#P2813. 奇妙的Fibonacci

    ID: 1930 传统题 1000ms 512MiB 尝试: 728 已通过: 159 难度: 7 上传者: 标签>CF2200提高欧几里得算法筛法计算积性函数线性筛约数个数乘积公式等比数列求和fib数

奇妙的Fibonacci

描述

Fibonacci 数列是这样一个数列:

  • F1=1, F2=1, F3=2, …F_1 = 1,~F_2 = 1,~F_3 = 2,~\dots

  • Fi=Fi−1+Fi−2 (i≥3)F_i = F_{i-1} + F_{i-2}~(i ≥ 3)

pty 突然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个 Fibonacci 数 FiF_i,有多少个 FjF_j 能够整除 FiF_i( ii 可以等于 jj ),他还想知道所有 jj 的平方之和是多少。

输入格式

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

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

  • 第 ii 个询问 Qi=(Qi−1×A+B) mod C+1 (i≥2)Q_i = (Q_{i-1} \times A + B) \bmod C + 1~(i ≥ 2)。

输出格式

  • AiA_i 代表第 ii 个询问有多少个 FjF_j 能够整除 FiF_i。

  • BiB_i 代表第 ii 个询问所有 jj 的平方之和。

输出包括两行:

  1. 第一行是所有的 AiA_i 之和。
  2. 第二行是所有的 BiB_i 之和。

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

示例输入

2
2 2 1 8

示例输出

6
55

提示

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