问题描述

梦梦给出了一个等差数列，其首项为 $x$，公差为 $d$，项数为 $N$。

熊熊在其中选了若干个数（可以不选，但每个数至多选一次），并求出了其和为 $S$，熊熊想知道通过这种方式得到的 $S$ 有多少种可能。

例如对于等差数列 $\{0,3\}$，选择的方案有 $\{\},\{0\},\{3\},\{0,3\}$，其和分别为 $0,0,3,3$，所以 $S$ 共有 $2$​ 种可能。

输入格式

输入共一行，包含 $3$ 个正整数，分别表示 $N,x,d$。

输出格式

输出一行，包含一个整数，表示答案。

样例输入1

2 0 3

样例输出1

2

样例解释1

合法的可能有 $0,3$。

样例输入2

20 1 2

样例输出2

399

样例输入3

1000 3 -2

样例输出3

996009

评测数据规模

对于 $20\%$ 的数据，$1 \leq N \leq 10$。

对于 $80\%$ 的数据，$1 \leq N \leq 1000$。

对于所有测评数据，$1 \leq N \leq 10^5,-10^8 \leq x,d \leq 10^8$。