数列求和(嘤雄难度)

题号：NC50052
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

给出数列A：

A₀=0,

A₁=2,

A_i=(3A_i-1- A_i-2)/2 + i + 1, (i>1)

给出n,m.

$求\sum_{i=1}^{n}{A_{i}(i与m互质)}$

答案对10⁹+7取模。

$1\leq n,m \leq 10^{8}$

多组测试样例(不多于15000组),每组一行两个整数n,m(保证n,m随机生成)。

对于每个测试样例，一行一个整数表示答案。

示例1

复制

4 4

复制

A₁+A₃=2+12=14