Description

Fibonacci数列是这样一个数列：

F1 = 1， F2 = 1， F3 = 2 . . .

Fi = Fi-1 + Fi-2 (当 i >= 3)

pty忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个Fibonacci数Fi，

有多少个Fj能够整除Fi (i可以等于j)，他还想知道所有j的平方之和是多少。

Format

Input

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

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

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

Output

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

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

输出包括两行：

第一行是所有的Ai之和。

第二行是所有的Bi之和。

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

Samples

2
2 2 1 8

6
55

Limitation

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