题目背景

车间的装箱任务排成了一长串。装箱规则写在一张旧卡片上：处理第 $i$ 个任务需要 $\left\lfloor \dfrac{a \cdot i + b}{m} \right\rfloor$ 只箱子。卡片上还留着 $a$、$b$、$m$ 三个参数，统计员却把算到一半的总数擦掉了。

题目描述

给定四个整数 $n, m, a, b$，其中 $1 \le n \le 10^{9}$，$2 \le m \le 10^{9}$，$0 \le a, b \le m - 1$。请求出

$$\sum_{i=0}^{n-1} \left\lfloor \frac{a \cdot i + b}{m} \right\rfloor .$$

保证结果不超过 $8 \times 10^{18}$。

输入格式

一行四个整数 $n, m, a, b$。

输出格式

一行一个整数，表示求和结果。

输入输出样例 #1

输入 #1

4 7 3 2

输出 #1

2

输入输出样例 #2

输入 #2

10 3 2 0

输出 #2

27

输入输出样例 #3

输入 #3

1 5 0 0

输出 #3

0

说明

样例解释

样例 1 中 $i$ 取 $0,1,2,3$，对应的 $\dfrac{3i+2}{7}$ 分别是 $\dfrac{2}{7},\dfrac{5}{7},\dfrac{8}{7},\dfrac{11}{7}$，向下取整后得到 $0,0,1,1$，总和为 $2$。

样例 2 中 $i$ 从 $0$ 到 $9$，$\left\lfloor \dfrac{2i}{3} \right\rfloor$ 依次为 $0,0,1,2,2,3,4,4,5,6$，总和为 $27$。

样例 3 中只有一项 $\left\lfloor \dfrac{0}{5} \right\rfloor = 0$，总和为 $0$。

数据范围

• 对于 $30\%$ 的数据，$n \le 1000$，$m \le 1000$；
• 对于 $60\%$ 的数据，$n \le 10^{6}$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^{9}$，$2 \le m \le 10^{9}$，$0 \le a, b \le m-1$。