#2813. 奇妙的Fibonacci

内存限制:512 MiB 时间限制:20 Sec

题目描述

Fibonacci数列是这样一个数列:
F1 = 1, F2 = 1, F3 = 2 . . .
Fi = Fi-1 + Fi-2 (当 i >= 3)
pty忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个Fibonacci数Fi,
有多少个Fj能够整除Fi (i可以等于j),他还想知道所有j的平方之和是多少。

输入格式

第一行一个整数Q,表示Q个询问。

第二行四个整数:Q1, A, B, C

i个询问Qi = (Qi-1 * A + B) mod C + 1(i >= 2)

输出格式

Ai代表第i个询问有多少个Fj能够整除FQi

Bi代表第i个询问所有j的平方之和。

输出包括两行:

第一行是所有的Ai之和。

第二行是所有的Bi之和。

由于答案过大,只需要输出除以1000000007得到的余数即可。

样例

样例输入


			
2
2 2 1 8


样例输出


			
6
55

数据范围与提示

对于100%的数据保证:Q <= 3*10^6,C <= 10^7,A <= 10^7,B <= 10^7,1 <= Q1<= C