Background

Description

liu_runda决定提高一下知识水平,于是他去请教郭神.郭神随手就给了liu_runda一道神题,liu_runda并不会做,于是把这个题扔到联考里给高二的做.
郭神有n 条位于第一象限内的线段,给出每条线段与 x 轴和y 轴交点的坐标,显然这样就可以唯一确定每一条线段.
n 条线段和y 轴交点的纵坐标分别为 1,2,3,4...n.我们记和y 轴交点纵坐标为 i 的线段和x轴交点的横坐标为x[i]+1,x[i]按这样的方式生成:
x[1]由输入给出.
x[i]=(x[i-1]+a) % mod,2<=i<=n.
即:如果x[3]=4,则与y轴交点纵坐标为3的抛物线,和x轴交点的横坐标4+1=5.
我们保证给出的n,x[1],a,mod使得所有的x[i]互不相同.
对于第一象限内的所有点(点的横纵坐标可以是任意实数),如果一个点被 x 条线段经过,它的鬼畜值就是x*(x-1)/2.
求第一象限内的所有点的鬼畜值之和.

Format

Input

一行4个整数n,x[1],a,mod

Output

1行一个整数表示鬼畜值之和.

Sample 1

Input

5 2 4 7

Output

5

Limitation

第1,2个测试点,n<=100.
第3,4个测试点,n<=10^5.
第5,6个测试点的数据,a<=10.
第7,8个测试点,x[1]=a.
第9,10个测试点,无特殊限制.
对于全 部 数 据 ,1<=n<=1e7,1<=a<=1e5,1<=mod<=1e8,a,mod 互质,n<mod,给出的n,x[1],a,mod使得所有的x[i]互不相同.
请选手注意,1e7个int类型的变量将占用大约40mb的内存,导致内存超限,本题得0分.
1s, 32000KiB for each test case.

Hint

Source

CDQZ TEST