Big Pattern Number

2 secs 1024 MB
OxOmiso's icon OxOmiso

問題文

22 以上の整数 nn と,11 以上の整数 aa が与えられます。
nn 進法で,以下の条件を満たす整数を X(n)X_{(n)} とします。X(n)X_{(n)} は一意に定まります。

  • 0r1+a×n0≤r≤-1+a×n を満たす rr について,X(n)X_{(n)}nrn^r の位が r(modn)r \hspace{1mm} (mod \hspace{1mm} n) である。

さて,nn 進数で表された X(n)X_{(n)} の, 1010 進数での値を 10000000071000000007 で割った余りで求めてください。
TT 個のテストケースが与えられるので,それぞれについて答えを求めてください。

例として,n=4,a=2n = 4 \hspace{1mm} , \hspace{1mm} a = 2 のとき,X(4)X_{(4)}3210321032103210 となります。このとき,X(10)X_{(10)} が求める答えであり,X(10)=4+32+192+1024+8192+49152=58596X_{(10)} = 4+32+192+1024+8192+49152=58596 となり,5859658596 が答えとなります。

作問者の想定解が誤っていました。制約を変更することで対応しました。申し訳ございません。

n,a1018n,a≤10^{18} を,n,a109n,a≤10^9 に変更しました。

制約

1T50001≤T≤5000
2n1092≤n≤10^{9}
1a1091≤a≤10^{9}

入力例 1

6
4 2
2 1 
10 5
4 10
3141592 65358979
1000000000 1000000000

出力例 1

58596
2
94746490
655820314
459742684
330625733

10000000071000000007 で割った余りを出力することを忘れないでください。

提出


Go (1.21)