【题目描述】

现有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. 求第一象限内的所有点的鬼畜值之和.

【输入格式】

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

【输出格式】

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

【样例输入1】(即sample1.in)

5 2 4 7

【样例输出1】(即sample1.ans)

5

【样例输入2】

见sample2.in,数据范围同第3,4个测试点

【样例输出2】

见sample2.ans

【样例输入3】

见sample3.in,数据范围同第5,6个测试点

【样例输出3】

见sample3.ans

【样例输入4】

见sample4.in,数据范围同第5,6个测试点

【样例输出4】

见sample4.ans

【样例输入5】

见sample5.in,数据范围同第5,6个测试点

【样例输出5】

见sample5.ans

样例下载fly-sample

【数据范围】

第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]互不相同.

请选手注意,本题内存可以优化到32M以内。