奇妙的Fibonacci

Fibonacci 数列是这样一个数列：

$F_1=1,\quad F_2=1,\quad F_3=2,\ \ldots$

$F_i=F_{i-1}+F_{i-2}\quad (i\ge 3).$

pty 忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个 Fibonacci 数 $F_i$，有多少个 $F_j$ 能够整除 $F_i$（$i$ 可以等于 $j$）；他还想知道所有这些 $j$ 的平方之和是多少。

输入格式

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

第二行四个整数 $Q_1, A, B, C$，其中第 $i$ 个询问为

$Q_i=(Q_{i-1}\times A+B)\bmod C+1\quad (i\ge 2).$

输出格式

记 $A_i$ 为第 $i$ 个询问中有多少个 $F_j$ 能够整除 $F_{Q_i}$，$B_i$ 为第 $i$ 个询问中所有这些 $j$ 的平方之和。

输出包括两行：第一行是所有 $A_i$ 之和，第二行是所有 $B_i$ 之和。

由于答案过大，只需要输出除以 $10^9+7$ 得到的余数即可。

样例输入

2
2  2  1  8

样例输出

6
55

样例解释

两个询问分别为 $Q_1=2$ 与 $Q_2=(2\times 2+1)\bmod 8+1=6$。

• $F_2=1$，能整除它的有 $F_1, F_2$，共 $2$ 个，对应 $j$ 的平方和为 $1^2+2^2=5$；
• $F_6=8$，能整除它的有 $F_1, F_2, F_3, F_6$（值分别为 $1, 1, 2, 8$），共 $4$ 个，对应 $j$ 的平方和为 $1^2+2^2+3^2+6^2=50$。

因此两行答案分别为 $2+4=6$ 与 $5+50=55$。

数据范围

对于 $100\%$ 的数据保证：

• $Q\le 3\times 10^6$；
• $A\le 10^7$，$B\le 10^7$，$C\le 10^7$；
• $1\le Q_1\le C$。

来源与许可

本题题面与测试数据整理自 BZOJ 2813。

样例 1

输入

2
2  2  1  8

输出

6
55