题目描述
令 (1+2)n=e(n)+2f(n),其中 e(n),f(n) 都是整数,显然有 (1−2)n=e(n)−2f(n)。令 g(n) 表示 f(1),f(2),⋯f(n) 的最小公倍数,给定两个正整数 n 和 p,其中 p 是质数,并且保证 f(1),f(2),⋯f(n) 在模 p 意义下均不为 0,请计算 i=1∑ni×g(i) 其在模 p 的值。
输入格式
第一行包含一个正整数 T ,表示有 T 组数据。
接下来是测试数据。每组测试数据只占一行,包含两个正整数 n 和 p 。
输出格式
对于每组测试数据,输出一行一个非负整数,表示这组数据的答案。
样例输入
5
1 233
2 233
3 233
4 233
5 233
样例输出
1
5
35
42
121
数据范围与约定
对于 100% 的数据,1≤T≤210,1≤n≤106,2≤p≤109+7,∑n≤3×106。
题目来源
鸣谢 Tangjz 提供试题