問題文
2 以上の整数 n と,1 以上の整数 a が与えられます。
n 進法で,以下の条件を満たす整数を X(n) とします。X(n) は一意に定まります。
- 0≤r≤−1+a×n を満たす r について,X(n) の nr の位が r(modn) である。
さて,n 進数で表された X(n) の, 10 進数での値を 1000000007 で割った余りで求めてください。
T 個のテストケースが与えられるので,それぞれについて答えを求めてください。
例として,n=4,a=2 のとき,X(4) は 32103210 となります。このとき,X(10) が求める答えであり,X(10)=4+32+192+1024+8192+49152=58596 となり,58596 が答えとなります。
作問者の想定解が誤っていました。制約を変更することで対応しました。申し訳ございません。
→n,a≤1018 を,n,a≤109 に変更しました。
制約
1≤T≤5000
2≤n≤109
1≤a≤109
入力例 1
6
4 2
2 1
10 5
4 10
3141592 65358979
1000000000 1000000000
出力例 1
58596
2
94746490
655820314
459742684
330625733
1000000007 で割った余りを出力することを忘れないでください。