题目描述

長さ $N$ の整数列 $A$ があり、$ A_1\ =\ X,\ A_{i+1}\ =\ A_i\ +\ D\ (1\ \leq\ i\ <\ N\ ) $ が成り立っています。

高橋君はこの整数列の要素をいくつか選んで取り、残り全てを青木君が取ります。$2$ 人のどちらかが全てを取ることになっても構いません。

高橋君の取った数の和を $S$, 青木君の取った数の和を $T$ としたとき、$S\ -\ T$ として考えられる値は何通りあるでしょうか。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $D$

输出格式

$S\ -\ T$ として考えられる値の種類数を出力せよ。

题目大意

给一个首项为$X$，公差为$D$，项数为$N$的等差数列$A$，定义

对于所有$S\subseteq \{1,2,...,N\}$，求有多少种不同的$w(S)$

3 4 2

8

2 3 -3

2

100 14 20

49805

提示

制約

• $-10^8\ \leq\ X,\ D\ \leq\ 10^8$
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• 入力は全て整数である

Sample Explanation 1

$A$ は $(4,\ 6,\ 8)$ です。 (高橋君, 青木君) の取り方は、 $ ((),\ (4,\ 6,\ 8)),\ ((4),\ (6,\ 8)),\ ((6),\ (4,\ 8)),\ ((8),\ (4,\ 6))),\ ((4,\ 6),\ (8))),\ ((4,\ 8),\ (6))),\ ((6,\ 8),\ (4))),\ ((4,\ 6,\ 8),\ ()) $ の $8$ 通りあります。 $S\ -\ T$ はそれぞれ $-18,\ -10,\ -6,\ -2,\ 2,\ 6,\ 10,\ 18$ であるので、値の種類数は $8$ です。

Sample Explanation 2

$A$ は $(3,\ 0)$ であり、$S\ -\ T$ として考えられる値は $-3,\ 3$ で、種類数は $2$ です。