题目描述

给定三个整数 $n$，$a$ 与 $d$，表示一个项数为 $n$ 的等差数列，首项为 $a$，公差为 $d$。

请统计，从这些数字中任意挑选一些（至少挑一个），将它们加起来，能形成多少种不同的和？

输入格式

• 三个整数： $n$，$a$ 与 $d$

输出格式

• 单个整数：表示子集和的种类数量

3 4 2

7

样例解释 1

等差序列为 {4, 6, 8} 能形成 7 种不同的子集和

数据范围

• $30\%$ 的数据，$1\leq n\leq 20$
• $60\%$ 的数据，$1\leq n\leq 500$，$1\leq d\leq 10$
• $100\%$ 的数据，$1\leq n\leq 300,000$
• $1\leq d\leq 10^6$
• $1\leq a\leq 10^6$