描述

Fibonacci 数列是这样一个数列：

• $F_1 = 1,~F_2 = 1,~F_3 = 2,~\dots$

• $F_i = F_{i-1} + F_{i-2}~(i ≥ 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~(i ≥ 2)$。

输出格式

• $A_i$ 代表第 $i$ 个询问有多少个 $F_j$ 能够整除 $F_i$。

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

输出包括两行：

1. 第一行是所有的 $A_i$ 之和。
2. 第二行是所有的 $B_i$ 之和。

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

示例输入

2
2 2 1 8

示例输出

6
55

提示

对于 $100\%$ 的数据保证：$Q ≤ 3\cdot10^6，C \le 10^7，A \le 10^7，B \le 10^7，1 \le Q_1 \le C$。