题目背景

DeepSeaSpray 的生日赛中有这么一道题：

给出$n$ 和$k$,设 $a_i=27\times \frac{3^i-1}{2}$，求$\sum\limits_{i=1}^{n}{i!}\times {k^{a_i}} \pmod {20090327}$

但是使用扩展欧拉定理的标程太慢了，毒瘤的 DengDuck 加强了数据。

题目描述

给出$n$ ，$k$和 $p$,设 $a_i=27\times \frac{3^i-1}{2}$，求$\sum\limits_{i=1}^{n}{i!}\times {k^{a_i}} \pmod {p}$^[1]

输入格式

本题有多组数据。

第一行给出一个多组数据的数量 $T$。

接下来 $T$ 行，每行

输出格式

总共有 $T$ 行，每行有一个正整数表示答案。

2
3 3 20090327
5 8 20090327

14287538
9903356

5
10 5 20090327
8 11 20090327
20000000 20000000 20090327
12050350 10030345 20090327
2000000 1000000000 20090327

12895494
16021812
6253276
7187435
8225178

7
5030262 29602 500028500
5008679 26660 500023462
5011707 34650 500022206
5004052 36409 500001197
5008237 10575 500016221
5015196 26838 500013595
5018043 9850 500013045

229824412
13767118
488656138
237576037
349203044
143710390
109628370

提示

$1\leq T\leq 10,1\leq n\leq 2\times 10^7$

$1\leq k\leq 10^7,1\leq p\leq 2\times 10^9$

本题不考虑数据阶梯。

数据很强，时限为 2500ms ，不要恶意提交。

本题请大力卡常。

特别说明

对 WangZiye,DeepSeaSpray,XieChenRui 没有任何看不起的意思，也没有贬低，辱骂，嘲讽的意思。

单纯是为了加强数据供练习。

希望不要误会。