結果
| 問題 | No.42 貯金箱の溜息 |
| ユーザー |
 vwxyz
|
| 提出日時 | 2021-08-21 08:11:06 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
AC
|
| 実行時間 | 133 ms / 5,000 ms |
| コード長 | 55,362 bytes |
| コンパイル時間 | 114 ms |
| コンパイル使用メモリ | 18,432 KB |
| 実行使用メモリ | 17,348 KB |
| 最終ジャッジ日時 | 2024-10-14 16:59:22 |
| 合計ジャッジ時間 | 1,265 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 125 ms
17,348 KB |
| testcase_01 | AC | 126 ms
16,960 KB |
| testcase_02 | AC | 133 ms
17,348 KB |
ソースコード
import bisect
import copy
import decimal
import fractions
import functools
import heapq
import itertools
import math
import random
import sys
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
if heap and item < heap[0]:
item, heap[0] = heap[0], item
heapq._siftup_max(heap, 0)
return item
from math import degrees, gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
def Extended_Euclid(n,m):
stack=[]
while m:
stack.append((n,m))
n,m=m,n%m
if n>=0:
x,y=1,0
else:
x,y=-1,0
for i in range(len(stack)-1,-1,-1):
n,m=stack[i]
x,y=y,x-(n//m)*y
return x,y
class MOD:
def __init__(self,mod):
self.mod=mod
def Pow(self,a,n):
a%=self.mod
if n>=0:
return pow(a,n,self.mod)
else:
assert math.gcd(a,self.mod)==1
x=Extended_Euclid(a,self.mod)[0]
return pow(x,-n,self.mod)
def Build_Fact(self,N):
assert N>=0
self.factorial=[1]
for i in range(1,N+1):
self.factorial.append((self.factorial[-1]*i)%self.mod)
self.factorial_inv=[None]*(N+1)
self.factorial_inv[-1]=self.Pow(self.factorial[-1],-1)
for i in range(N-1,-1,-1):
self.factorial_inv[i]=(self.factorial_inv[i+1]*(i+1))%self.mod
return self.factorial_inv
def Fact(self,N):
return self.factorial[N]
def Fact_Inv(self,N):
return self.factorial_inv[N]
def Comb(self,N,K):
if K<0 or K>N:
return 0
s=self.factorial[N]
s=(s*self.factorial_inv[K])%self.mod
s=(s*self.factorial_inv[N-K])%self.mod
return s
class Lagrange_Interpolation:
def __init__(self,X=False,lst=False,x0=None,xd=None,mod=0):
self.degree=len(lst)-1
self.mod=mod
assert xd>0
self.X=[(x0+i*xd)%self.mod for i in range(self.degree+1)]
self.coefficient=lst
def __getitem__(self,N):
N%=self.mod
XX=[N-x for x in self.X]
XX_left=[1]*(self.degree+2)
for i in range(1,self.degree+2):
XX_left[i]=XX_left[i-1]*XX[i-1]%self.mod
XX_right=[1]*(self.degree+2)
for i in range(self.degree,-1,-1):
XX_right[i]=XX_right[i+1]*XX[i]%self.mod
return sum(XX_left[i]*XX_right[i+1]*self.coefficient[i] for i in range(self.degree+1))%self.mod
def NTT(polynomial1,polynomial2):
prim_root=3
prim_root_inve=MOD(mod).Pow(prim_root,-1)
def DFT(polynomial,inverse=False):
dft=polynomial+[0]*((1<<n)-len(polynomial))
if inverse:
for bit in range(1,n+1):
a=1<<bit-1
x=pow(prim_root,mod-1>>bit,mod)
U=[1]
for _ in range(a):
U.append(U[-1]*x%mod)
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
dft[s],dft[t]=(dft[s]+dft[t]*U[j])%mod,(dft[s]-dft[t]*U[j])%mod
else:
for bit in range(n,0,-1):
a=1<<bit-1
x=pow(prim_root_inve,mod-1>>bit,mod)
U=[1]
for _ in range(a):
U.append(U[-1]*x%mod)
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
dft[s],dft[t]=(dft[s]+dft[t])%mod,U[j]*(dft[s]-dft[t])%mod
return dft
N=len(polynomial1)+len(polynomial2)-1
n=(N-1).bit_length()
ntt=[x*y%mod for x,y in zip(DFT(polynomial1),DFT(polynomial2))]
ntt=DFT(ntt,inverse=True)
x=pow((mod+1)//2,n)
ntt=[ntt[i]*x%mod for i in range(N)]
return ntt
def FFT(polynomial1,polynomial2,digit=10**5):
def DFT(polynomial,n,inverse=False):
N=len(polynomial)
if inverse:
primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
else:
primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]
dft=polynomial+[0]*((1<<n)-N)
if inverse:
for bit in range(1,n+1):
a=1<<bit-1
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
dft[s],dft[t]=dft[s]+dft[t]*primitive_root[j<<n-bit],dft[s]-dft[t]*primitive_root[j<<n-bit]
else:
for bit in range(n,0,-1):
a=1<<bit-1
for i in range(1<<n-bit):
for j in range(a):
s=i*2*a+j
t=s+a
dft[s],dft[t]=dft[s]+dft[t],primitive_root[j<<n-bit]*(dft[s]-dft[t])
return dft
def FFT_(polynomial1,polynomial2):
N1=len(polynomial1)
N2=len(polynomial2)
N=N1+N2-1
n=(N-1).bit_length()
fft=[x*y for x,y in zip(DFT(polynomial1,n),DFT(polynomial2,n))]
fft=DFT(fft,n,inverse=True)
fft=[round((fft[i]/(1<<n)).real) for i in range(N)]
return fft
N1=len(polynomial1)
N2=len(polynomial2)
N=N1+N2-1
polynomial11,polynomial12=[None]*N1,[None]*N1
polynomial21,polynomial22=[None]*N2,[None]*N2
for i in range(N1):
polynomial11[i],polynomial12[i]=divmod(polynomial1[i],digit)
for i in range(N2):
polynomial21[i],polynomial22[i]=divmod(polynomial2[i],digit)
polynomial=[0]*(N)
a=digit**2-digit
for i,x in enumerate(FFT_(polynomial11,polynomial21)):
polynomial[i]+=x*a
a=digit-1
for i,x in enumerate(FFT_(polynomial12,polynomial22)):
polynomial[i]-=x*a
for i,x in enumerate(FFT_([x1+x2 for x1,x2 in zip(polynomial11,polynomial12)],[x1+x2 for x1,x2 in zip(polynomial21,polynomial22)])):
polynomial[i]+=x*digit
return polynomial
def Primitive_Root(p):
if p==2:
return 1
if p==167772161:
return 3
if p==469762049:
return 3
if p==754974721:
return 11
if p==998244353:
return 3
if p==10**9+7:
return 5
divisors=[2]
pp=(p-1)//2
while pp%2==0:
pp//=2
for d in range(3,pp+1,2):
if d**2>pp:
break
if pp%d==0:
divisors.append(d)
while pp%d==0:
pp//=d
if pp>1:
divisors.append(pp)
primitive_root=2
while True:
for d in divisors:
if pow(primitive_root,(p-1)//d,p)==1:
break
else:
return primitive_root
primitive_root+=1
class Polynomial:
def __init__(self,polynomial,max_degree=-1,eps=1e-12,mod=0):
self.max_degree=max_degree
if self.max_degree!=-1 and len(polynomial)>self.max_degree+1:
self.polynomial=polynomial[:self.max_degree+1]
else:
self.polynomial=polynomial
self.mod=mod
self.eps=eps
def __eq__(self,other):
if type(other)!=Polynomial:
return False
if len(self.polynomial)!=len(other.polynomial):
return False
for i in range(len(self.polynomial)):
if abs(self.polynomial[i]-other.polynomial[i])>self.eps:
return False
return True
def __ne__(self,other):
if type(other)!=Polynomial:
return True
if len(self.polynomial)!=len(other.polynomial):
return True
for i in range(len(self.polynomial)):
if abs(self.polynomial[i]-other.polynomial[i])>self.eps:
return True
return False
def __add__(self,other):
assert type(other)==Polynomial
summ=[0]*max(len(self.polynomial),len(other.polynomial))
for i in range(len(self.polynomial)):
summ[i]+=self.polynomial[i]
for i in range(len(other.polynomial)):
summ[i]+=other.polynomial[i]
if self.mod:
for i in range(len(summ)):
summ[i]%=self.mod
while summ and abs(summ[-1])<self.eps:
summ.pop()
summ=Polynomial(summ,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return summ
def __sub__(self,other):
assert type(other)==Polynomial
diff=[0]*max(len(self.polynomial),len(other.polynomial))
for i in range(len(self.polynomial)):
diff[i]+=self.polynomial[i]
for i in range(len(other.polynomial)):
diff[i]-=other.polynomial[i]
if self.mod:
for i in range(len(diff)):
diff[i]%=self.mod
while diff and abs(diff[-1])<self.eps:
diff.pop()
diff=Polynomial(diff,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return diff
def __mul__(self,other):
if type(other)==Polynomial:
if self.max_degree==-1:
prod=[0]*(len(self.polynomial)+len(other.polynomial)-1)
for i in range(len(self.polynomial)):
for j in range(len(other.polynomial)):
prod[i+j]+=self.polynomial[i]*other.polynomial[j]
else:
prod=[0]*min(len(self.polynomial)+len(other.polynomial)-1,self.max_degree+1)
for i in range(len(self.polynomial)):
for j in range(min(len(other.polynomial),self.max_degree+1-i)):
prod[i+j]+=self.polynomial[i]*other.polynomial[j]
if self.mod:
for i in range(len(prod)):
prod[i]%=self.mod
while prod and abs(prod[-1])<self.eps:
prod.pop()
else:
if self.mod:
prod=[x*other%self.mod for x in self.polynomial]
else:
prod=[x*other for x in self.polynomial]
while prod and abs(prod[-1])<self.eps:
prod.pop()
prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return prod
def __matmul__(self,other):
assert type(other)==Polynomial
if self.mod:
prod=NTT(self.polynomial,other.polynomial)
else:
prod=FFT(self.polynomial,other.polynomial)
if self.max_degree!=-1 and len(prod)>self.max_degree+1:
prod=prod[:self.max_degree+1]
while prod and abs(prod[-1])<self.eps:
prod.pop()
prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return prod
def __truediv__(self,other):
if type(other)==Polynomial:
assert other.polynomial
for n in range(len(other.polynomial)):
if self.eps<abs(other.polynomial[n]):
break
assert len(self.polynomial)>n
for i in range(n):
assert abs(self.polynomial[i])<self.eps
self_polynomial=self.polynomial[n:]
other_polynomial=other.polynomial[n:]
if self.mod:
inve=MOD(self.mod).Pow(other_polynomial[0],-1)
else:
inve=1/other_polynomial[0]
quot=[]
for i in range(len(self_polynomial)-len(other_polynomial)+1):
if self.mod:
quot.append(self_polynomial[i]*inve%self.mod)
else:
quot.append(self_polynomial[i]*inve)
for j in range(len(other_polynomial)):
self_polynomial[i+j]-=other_polynomial[j]*quot[-1]
if self.mod:
self_polynomial[i+j]%=self.mod
for i in range(len(self_polynomial)-len(other_polynomial)+1,len(self_polynomial)):
if self.eps<abs(self_polynomial[i]):
assert self.max_degree!=-1
self_polynomial=self_polynomial[-len(other_polynomial)+1:]
while len(quot)<=self.max_degree:
self_polynomial.append(0)
if self.mod:
quot.append(self_polynomial[0]*inve%self.mod)
self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1])%self.mod for i in range(1,len(self_polynomial))]
else:
quot.append(self_polynomial[0]*inve)
self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1]) for i in range(1,len(self_polynomial))]
break
quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
else:
assert self.eps<abs(other)
if self.mod:
inve=MOD(self.mod).Pow(other,-1)
quot=Polynomial([x*inve%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)
else:
quot=Polynomial([x/other for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return quot
def __floordiv__(self,other):
assert type(other)==Polynomial
quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
rema=[x for x in self.polynomial]
if self.mod:
inve=MOD(self.mod).Pow(other.polynomial[-1],-1)
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve%self.mod
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
rema[i+j]%=self.mod
else:
inve=1/other.polynomial[-1]
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return quot
def __mod__(self,other):
assert type(other)==Polynomial
quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
rema=[x for x in self.polynomial]
if self.mod:
inve=MOD(self.mod).Pow(other.polynomial[-1],-1)
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve%self.mod
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
rema[i+j]%=self.mod
rema.pop()
else:
inve=1/other.polynomial[-1]
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
rema.pop()
rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return rema
def __divmod__(self,other):
assert type(other)==Polynomial
quot=[0]*(len(self.polynomial)-len(other.polynomial)+1)
rema=[x for x in self.polynomial]
if self.mod:
inve=MOD(self.mod).Pow(other.polynomial[-1],-1)
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve%self.mod
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
rema[i+j]%=self.mod
rema.pop()
else:
inve=1/other.polynomial[-1]
for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):
quot[i]=rema[i+len(other.polynomial)-1]*inve
for j in range(len(other.polynomial)):
rema[i+j]-=quot[i]*other.polynomial[j]
rema.pop()
quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return quot,rema
def __neg__(self):
if self.mod:
nega=Polynomial([(-x)%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)
else:
nega=Polynomial([-x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return nega
def __pos__(self):
posi=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)
return posi
def __bool__(self):
return self.polynomial
def __getitem__(self,n):
if n<=len(self.polynomial)-1:
return self.polynomial[n]
else:
return 0
def __setitem__(self,n,x):
if self.mod:
x%=self.mod
if self.max_degree==-1 or n<=self.max_degree:
if n<=len(self.polynomial)-1:
self.polynomial[n]=x
elif self.eps<abs(x):
self.polynomial+=[0]*(n-len(self.polynomial))+[x]
def __call__(self,x):
retu=0
pow_x=1
for i in range(len(self.polynomial)):
retu+=pow_x*self.polynomial[i]
pow_x*=x
if self.mod:
retu%=self.mod
pow_x%=self.mod
return retu
def __str__(self):
return "["+", ".join(map(str,self.polynomial))+"]"
def Bostan_Mori(poly_deno,poly_nume,N,mod=0,fft=False,ntt=False):
if type(poly_deno)==Polynomial:
poly_deno=poly_deno.polynomial
if type(poly_nume)==Polynomial:
poly_nume=poly_nume.polynomial
if ntt:
convolve=NTT
elif fft:
convolve=FFT
else:
def convolve(poly_deno,poly_nume):
conv=[0]*(len(poly_deno)+len(poly_nume)-1)
for i in range(len(poly_deno)):
for j in range(len(poly_nume)):
conv[i+j]+=poly_deno[i]*poly_nume[j]
if mod:
for i in range(len(conv)):
conv[i]%=mod
return conv
while N:
poly_nume_=[-x if i%2 else x for i,x in enumerate(poly_nume)]
if N%2:
poly_deno=convolve(poly_deno,poly_nume_)[1::2]
else:
poly_deno=convolve(poly_deno,poly_nume_)[::2]
poly_nume=convolve(poly_nume,poly_nume_)[::2]
if fft and mod:
for i in range(len(poly_deno)):
poly_deno[i]%=mod
for i in range(len(poly_nume)):
poly_nume[i]%=mod
N//=2
return poly_deno[0]
mod=10**9+9
LI={0: [662551443, 946817490, 530900153, 762902525, 202578521, 34990637], 1: [662551443, 946817490, 530900153, 762902525, 202578521, 34990637], 2: [662551443, 946817490, 530900153, 762902525, 202578521, 34990637], 3: [662551443, 946817490, 530900153, 762902525, 202578521, 34990637], 4: [662551443, 946817490, 530900153, 762902525, 202578521, 34990637], 5: [325102877, 901560897, 555429931, 919879119, 576268154, 862499800], 6: [325102877, 901560897, 555429931, 919879119, 576268154, 862499800], 7: [325102877, 901560897, 555429931, 919879119, 576268154, 862499800], 8: [325102877, 901560897, 555429931, 919879119, 576268154, 862499800], 9: [325102877, 901560897, 555429931, 919879119, 576268154, 862499800], 10: [650205754, 284288447, 411230226, 113906371, 357351115, 323758847], 11: [650205754, 284288447, 411230226, 113906371, 357351115, 323758847], 12: [650205754, 284288447, 411230226, 113906371, 357351115, 323758847], 13: [650205754, 284288447, 411230226, 113906371, 357351115, 323758847], 14: [650205754, 284288447, 411230226, 113906371, 357351115, 323758847], 15: [975308631, 667016006, 267030521, 307933632, 138434076, 785017903], 16: [975308631, 667016006, 267030521, 307933632, 138434076, 785017903], 17: [975308631, 667016006, 267030521, 307933632, 138434076, 785017903], 18: [975308631, 667016006, 267030521, 307933632, 138434076, 785017903], 19: [975308631,
667016006, 267030521, 307933632, 138434076, 785017903], 20: [962962942, 477727708, 954101342, 539011560, 326910374, 880026852], 21: [962962942, 477727708, 954101342, 539011560, 326910374, 880026852], 22: [962962942, 477727708, 954101342, 539011560, 326910374, 880026852], 23: [962962942, 477727708, 954101342, 539011560, 326910374, 880026852], 24: [962962942, 477727708, 954101342, 539011560, 326910374, 880026852], 25: [950617253, 288439410, 641172154, 770089488, 515386672, 975035801], 26: [950617253, 288439410, 641172154, 770089488, 515386672,
975035801], 27: [950617253, 288439410, 641172154, 770089488, 515386672, 975035801], 28: [950617253, 288439410, 641172154, 770089488, 515386672, 975035801], 29: [950617253, 288439410, 641172154, 770089488, 515386672, 975035801], 30: [600822998, 527135264, 159513483, 38218074, 111256298, 703794643], 31: [600822998, 527135264, 159513483, 38218074, 111256298, 703794643], 32: [600822998, 527135264, 159513483, 38218074, 111256298, 703794643], 33: [600822998, 527135264, 159513483, 38218074, 111256298, 703794643], 34: [600822998, 527135264, 159513483, 38218074, 111256298, 703794643], 35: [251028743, 765831118, 677854821, 306346669, 707125933, 432553485], 36: [251028743, 765831118, 677854821, 306346669, 707125933, 432553485], 37: [251028743, 765831118, 677854821, 306346669, 707125933, 432553485], 38: [251028743, 765831118, 677854821, 306346669, 707125933, 432553485], 39: [251028743, 765831118, 677854821, 306346669, 707125933, 432553485], 40: [563785931,
432511115, 27466667, 611525931, 710388896, 795062229], 41: [563785931, 432511115, 27466667, 611525931, 710388896, 795062229], 42: [563785931, 432511115, 27466667, 611525931, 710388896, 795062229], 43: [563785931, 432511115, 27466667, 611525931, 710388896, 795062229], 44: [563785931, 432511115, 27466667, 611525931, 710388896, 795062229], 45: [876543119, 99191112, 377078522, 916705193, 713651859, 157570964], 46: [876543119, 99191112, 377078522, 916705193, 713651859, 157570964], 47: [876543119, 99191112, 377078522, 916705193, 713651859, 157570964], 48: [876543119, 99191112, 377078522, 916705193, 713651859, 157570964], 49: [876543119, 99191112, 377078522, 916705193, 713651859, 157570964], 50: [514403175, 4554963, 817219563, 991446527, 325953337, 487163204], 51: [514403175, 4554963, 817219563, 991446527, 325953337,
487163204], 52: [514403175, 4554963, 817219563, 991446527, 325953337, 487163204], 53: [514403175, 4554963, 817219563, 991446527, 325953337, 487163204], 54: [514403175, 4554963, 817219563, 991446527, 325953337, 487163204], 55: [152263231, 909918823, 257360595, 66187852, 938254824, 816755444], 56: [152263231, 909918823, 257360595, 66187852, 938254824, 816755444], 57: [152263231, 909918823, 257360595, 66187852, 938254824, 816755444], 58: [152263231, 909918823, 257360595, 66187852, 938254824, 816755444], 59: [152263231, 909918823, 257360595, 66187852, 938254824, 816755444], 60: [115226164, 53966519, 788030822, 910491267, 159594817, 113431171], 61: [115226164, 53966519, 788030822,
910491267, 159594817, 113431171], 62: [115226164, 53966519, 788030822, 910491267, 159594817, 113431171], 63: [115226164, 53966519, 788030822, 910491267, 159594817, 113431171], 64: [115226164, 53966519, 788030822, 910491267, 159594817, 113431171], 65: [78189097, 198014224, 318701040, 754794673, 380934819, 410106907], 66: [78189097, 198014224, 318701040, 754794673, 380934819, 410106907], 67: [78189097, 198014224, 318701040, 754794673, 380934819, 410106907], 68: [78189097, 198014224, 318701040, 754794673, 380934819, 410106907], 69: [78189097, 198014224, 318701040, 754794673, 380934819, 410106907], 70: [366254907, 580745783, 939900453, 368660151, 211313336, 673866139], 71: [366254907, 580745783, 939900453, 368660151, 211313336, 673866139], 72: [366254907, 580745783, 939900453, 368660151, 211313336, 673866139], 73:
[366254907, 580745783, 939900453, 368660151, 211313336, 673866139], 74: [366254907, 580745783, 939900453, 368660151, 211313336, 673866139], 75: [654320717, 963477342, 561099857, 982525638, 41691853, 937625371], 76: [654320717, 963477342, 561099857, 982525638, 41691853, 937625371], 77: [654320717, 963477342, 561099857, 982525638, 41691853, 937625371], 78: [654320717, 963477342, 561099857, 982525638, 41691853, 937625371], 79: [654320717, 963477342, 561099857, 982525638, 41691853, 937625371], 80: [267489395, 584892746, 272828447, 365953188, 481108894, 168468090], 81: [267489395, 584892746, 272828447, 365953188, 481108894, 168468090], 82: [267489395, 584892746, 272828447, 365953188, 481108894, 168468090], 83: [267489395, 584892746, 272828447, 365953188, 481108894, 168468090], 84: [267489395, 584892746, 272828447, 365953188, 481108894, 168468090], 85: [880658082, 206308150, 984557046, 749380747, 920525935, 399310818], 86: [880658082, 206308150, 984557046, 749380747, 920525935, 399310818], 87: [880658082, 206308150, 984557046, 749380747, 920525935, 399310818], 88: [880658082, 206308150, 984557046, 749380747, 920525935, 399310818], 89: [880658082, 206308150, 984557046, 749380747, 920525935, 399310818], 90: [818929637, 66407408, 786814822, 902370378, 968981491, 597237042], 91: [818929637, 66407408, 786814822, 902370378, 968981491, 597237042], 92: [818929637, 66407408, 786814822, 902370378, 968981491, 597237042], 93: [818929637, 66407408, 786814822, 902370378, 968981491, 597237042], 94: [818929637, 66407408, 786814822, 902370378, 968981491, 597237042], 95: [757201192, 926506675, 589072598, 55360000, 17437038, 795163266], 96:
[757201192, 926506675, 589072598, 55360000, 17437038, 795163266], 97: [757201192, 926506675, 589072598, 55360000, 17437038, 795163266], 98: [757201192, 926506675, 589072598, 55360000, 17437038, 795163266], 99: [757201192, 926506675, 589072598, 55360000, 17437038, 795163266], 100: [345678492, 210475113, 617661339, 208365631, 440362227, 318197958], 101: [345678492, 210475113, 617661339, 208365631, 440362227, 318197958], 102: [345678492, 210475113, 617661339, 208365631, 440362227, 318197958], 103: [345678492, 210475113, 617661339, 208365631, 440362227, 318197958], 104: [345678492, 210475113, 617661339, 208365631, 440362227, 318197958], 105: [934155801, 494443560, 646250080, 361371262, 863287416, 841232659], 106: [934155801, 494443560, 646250080, 361371262, 863287416, 841232659], 107: [934155801, 494443560, 646250080, 361371262, 863287416, 841232659], 108: [934155801, 494443560, 646250080, 361371262, 863287416, 841232659], 109: [934155801, 494443560, 646250080, 361371262, 863287416, 841232659], 110: [172838846, 202281187, 901169786, 514392893, 660682229, 689375828], 111: [172838846,
202281187, 901169786, 514392893, 660682229, 689375828], 112: [172838846, 202281187, 901169786, 514392893, 660682229, 689375828], 113: [172838846, 202281187, 901169786, 514392893, 660682229, 689375828], 114: [172838846, 202281187, 901169786, 514392893, 660682229, 689375828], 115: [411521900, 910118823, 156089483, 667414524, 458077042, 537518997], 116: [411521900, 910118823, 156089483, 667414524, 458077042, 537518997], 117: [411521900, 910118823, 156089483, 667414524, 458077042, 537518997], 118: [411521900, 910118823, 156089483, 667414524, 458077042, 537518997], 119: [411521900, 910118823, 156089483, 667414524, 458077042, 537518997], 120: [300410699, 41825630, 637340154, 820452155, 629941488, 710770643], 121: [300410699, 41825630, 637340154, 820452155, 629941488, 710770643], 122: [300410699, 41825630, 637340154,
820452155, 629941488, 710770643], 123: [300410699, 41825630, 637340154, 820452155, 629941488, 710770643], 124: [300410699, 41825630, 637340154, 820452155, 629941488, 710770643], 125: [189299498, 173532446, 118590816, 973489786, 801805934, 884022289], 126: [189299498, 173532446, 118590816, 973489786, 801805934, 884022289], 127: [189299498, 173532446, 118590816, 973489786, 801805934, 884022289], 128: [189299498, 173532446, 118590816, 973489786, 801805934, 884022289], 129: [189299498, 173532446, 118590816, 973489786, 801805934, 884022289], 130:
[728394051, 729108451, 826172452, 126543408, 348140004, 382382403], 131: [728394051, 729108451, 826172452, 126543408, 348140004, 382382403], 132: [728394051, 729108451, 826172452, 126543408, 348140004, 382382403], 133: [728394051, 729108451, 826172452, 126543408, 348140004, 382382403], 134: [728394051, 729108451, 826172452, 126543408, 348140004, 382382403], 135: [267488595, 284684447, 533754079, 279597039, 894474083, 880742526], 136: [267488595, 284684447, 533754079, 279597039, 894474083, 880742526], 137: [267488595, 284684447, 533754079, 279597039, 894474083, 880742526], 138: [267488595, 284684447, 533754079, 279597039, 894474083, 880742526], 139: [267488595, 284684447, 533754079, 279597039, 894474083, 880742526], 140: [456788893, 264129632, 467666671, 432666670, 815277786, 704211117], 141: [456788893, 264129632, 467666671, 432666670, 815277786, 704211117], 142: [456788893, 264129632, 467666671, 432666670, 815277786, 704211117], 143: [456788893, 264129632, 467666671, 432666670, 815277786, 704211117], 144: [456788893, 264129632, 467666671, 432666670, 815277786, 704211117], 145: [646089191, 243574817, 401579263, 585736301, 736081489, 527679708], 146: [646089191, 243574817, 401579263, 585736301, 736081489, 527679708], 147: [646089191, 243574817, 401579263, 585736301, 736081489, 527679708], 148: [646089191, 243574817, 401579263, 585736301, 736081489,
527679708], 149: [646089191, 243574817, 401579263, 585736301, 736081489, 527679708], 150: [810698111, 832074526, 697624599, 969275860, 796785934, 34281748], 151: [810698111, 832074526, 697624599, 969275860, 796785934, 34281748], 152: [810698111, 832074526, 697624599, 969275860, 796785934, 34281748], 153: [810698111, 832074526, 697624599, 969275860, 796785934, 34281748], 154: [810698111, 832074526, 697624599, 969275860, 796785934, 34281748], 155: [975307031, 420574226, 993669935, 352815410, 857490379, 540883797], 156: [975307031, 420574226, 993669935, 352815410, 857490379, 540883797], 157: [975307031, 420574226, 993669935, 352815410, 857490379, 540883797], 158: [975307031, 420574226, 993669935, 352815410, 857490379, 540883797], 159: [975307031, 420574226, 993669935, 352815410, 857490379, 540883797], 160: [115224564, 618128450, 651848006, 966824897, 58095557, 730619295], 161: [115224564, 618128450, 651848006, 966824897, 58095557, 730619295], 162:
[115224564, 618128450, 651848006, 966824897, 58095557, 730619295], 163: [115224564, 618128450, 651848006, 966824897, 58095557, 730619295], 164: [115224564, 618128450, 651848006, 966824897, 58095557, 730619295], 165: [255142106, 815682674, 310026077, 580834375, 258700744, 920354793], 166: [255142106, 815682674, 310026077, 580834375, 258700744, 920354793], 167: [255142106, 815682674, 310026077, 580834375, 258700744, 920354793], 168: [255142106, 815682674, 310026077, 580834375, 258700744, 920354793], 169: [255142106, 815682674, 310026077, 580834375, 258700744, 920354793], 170: [370368270, 622291413, 330336892, 425313781, 599206673, 793223740], 171: [370368270, 622291413, 330336892, 425313781, 599206673, 793223740], 172: [370368270, 622291413, 330336892, 425313781, 599206673, 793223740], 173: [370368270, 622291413, 330336892, 425313781, 599206673, 793223740], 174: [370368270, 622291413, 330336892, 425313781, 599206673, 793223740], 175: [485594434, 428900152, 350647707, 269793187, 939712602, 666092687], 176: [485594434, 428900152, 350647707, 269793187, 939712602, 666092687], 177: [485594434, 428900152, 350647707, 269793187, 939712602, 666092687], 178: [485594434, 428900152, 350647707, 269793187, 939712602, 666092687],
179: [485594434, 428900152, 350647707, 269793187, 939712602, 666092687], 180: [576129220, 844563415, 733091266, 344742521, 420119264, 222095083], 181: [576129220, 844563415, 733091266, 344742521, 420119264, 222095083], 182: [576129220, 844563415, 733091266, 344742521, 420119264, 222095083], 183: [576129220, 844563415, 733091266, 344742521, 420119264, 222095083], 184: [576129220, 844563415, 733091266, 344742521, 420119264, 222095083], 185: [666664006, 260226669, 115534816, 419691855, 900525935, 778097488], 186: [666664006, 260226669, 115534816, 419691855, 900525935, 778097488], 187: [666664006, 260226669, 115534816, 419691855, 900525935, 778097488], 188: [666664006, 260226669,
115534816, 419691855, 900525935, 778097488], 189: [666664006, 260226669, 115534816, 419691855, 900525935, 778097488], 190: [732507414, 284944447, 860111119, 725111117, 520833339, 17233333], 191: [732507414, 284944447, 860111119, 725111117, 520833339, 17233333], 192: [732507414, 284944447, 860111119, 725111117, 520833339, 17233333], 193: [732507414, 284944447, 860111119, 725111117, 520833339, 17233333], 194:
[732507414, 284944447, 860111119, 725111117, 520833339, 17233333], 195: [798350822, 309662225, 604687413, 30530370, 141140743, 256369187], 196: [798350822, 309662225, 604687413, 30530370, 141140743, 256369187], 197: [798350822, 309662225, 604687413, 30530370, 141140743, 256369187], 198: [798350822, 309662225, 604687413, 30530370, 141140743, 256369187], 199: [798350822, 309662225, 604687413, 30530370, 141140743, 256369187], 200: [827157163, 503105486, 723741340, 294816002, 230565929, 561354849], 201: [827157163, 503105486, 723741340, 294816002, 230565929, 561354849], 202: [827157163, 503105486, 723741340, 294816002, 230565929, 561354849], 203: [827157163, 503105486, 723741340,
294816002, 230565929, 561354849], 204: [827157163, 503105486, 723741340, 294816002, 230565929, 561354849], 205: [855963504, 696548747, 842795267, 559101634, 319991115, 866340511], 206: [855963504, 696548747, 842795267, 559101634, 319991115, 866340511], 207: [855963504, 696548747, 842795267, 559101634, 319991115, 866340511], 208: [855963504, 696548747, 842795267, 559101634, 319991115, 866340511], 209: [855963504, 696548747, 842795267, 559101634, 319991115, 866340511], 210: [847732778, 58717482, 336326818, 782253636, 878534083, 237175972], 211: [847732778, 58717482, 336326818, 782253636, 878534083, 237175972], 212: [847732778, 58717482, 336326818, 782253636, 878534083, 237175972], 213: [847732778, 58717482, 336326818, 782253636, 878534083, 237175972], 214: [847732778, 58717482, 336326818, 782253636, 878534083, 237175972], 215: [839502052, 420886226, 829858378, 5405629, 437077042, 608011442], 216: [839502052, 420886226, 829858378, 5405629, 437077042, 608011442], 217: [839502052, 420886226, 829858378, 5405629, 437077042, 608011442], 218: [839502052, 420886226, 829858378, 5405629, 437077042, 608011442], 219: [839502052, 420886226, 829858378, 5405629, 437077042, 608011442], 220: [794234259, 951780453, 697867562, 187424001, 464737783, 44696711], 221: [794234259, 951780453, 697867562, 187424001, 464737783, 44696711], 222: [794234259, 951780453, 697867562,
187424001, 464737783, 44696711], 223: [794234259, 951780453, 697867562, 187424001, 464737783, 44696711], 224: [794234259, 951780453, 697867562, 187424001, 464737783, 44696711], 225: [748966466, 482674671, 565876746, 369442373, 492398524, 481381989], 226: [748966466, 482674671, 565876746, 369442373, 492398524, 481381989], 227: [748966466, 482674671, 565876746, 369442373, 492398524, 481381989], 228: [748966466, 482674671, 565876746, 369442373, 492398524, 481381989], 229: [748966466, 482674671, 565876746, 369442373, 492398524, 481381989], 230: [666661606, 182294372, 808363563, 510327115, 989177047, 983917075], 231: [666661606, 182294372, 808363563, 510327115, 989177047, 983917075], 232: [666661606, 182294372, 808363563, 510327115, 989177047, 983917075], 233: [666661606, 182294372, 808363563, 510327115, 989177047,
983917075], 234: [666661606, 182294372, 808363563, 510327115, 989177047, 983917075], 235: [584356746, 881914082, 50850371, 651211857, 485955561, 486452152], 236: [584356746, 881914082, 50850371, 651211857, 485955561, 486452152], 237: [584356746, 881914082, 50850371, 651211857, 485955561, 486452152], 238: [584356746, 881914082, 50850371, 651211857, 485955561, 486452152], 239: [584356746, 881914082, 50850371,
651211857, 485955561, 486452152], 240: [465014819, 750259266, 667814821, 750962969, 451851857, 54837037], 241: [465014819, 750259266, 667814821, 750962969, 451851857, 54837037], 242: [465014819, 750259266, 667814821, 750962969, 451851857, 54837037], 243: [465014819, 750259266, 667814821, 750962969, 451851857, 54837037], 244: [465014819, 750259266, 667814821, 750962969, 451851857, 54837037], 245: [345672892,
618604450, 284779262, 850714081, 417748153, 623221931], 246: [345672892, 618604450, 284779262, 850714081, 417748153, 623221931], 247: [345672892, 618604450, 284779262, 850714081, 417748153, 623221931], 248: [345672892, 618604450, 284779262, 850714081, 417748153, 623221931], 249: [345672892, 618604450, 284779262, 850714081, 417748153, 623221931], 250: [176948209, 215346076, 288566225, 637728005, 181979262, 640172983], 251: [176948209, 215346076, 288566225, 637728005, 181979262, 640172983], 252: [176948209, 215346076, 288566225, 637728005, 181979262, 640172983], 253: [176948209, 215346076, 288566225, 637728005, 181979262, 640172983], 254: [176948209, 215346076, 288566225, 637728005, 181979262, 640172983], 255: [8223526, 812087711, 292353188, 424741929, 946210380, 657124035], 256: [8223526, 812087711, 292353188, 424741929, 946210380, 657124035], 257: [8223526, 812087711, 292353188, 424741929, 946210380, 657124035], 258: [8223526, 812087711, 292353188, 424741929, 946210380, 657124035], 259: [8223526, 812087711, 292353188, 424741929, 946210380, 657124035], 260: [790116096, 137225779,
682962673, 899018674, 508776302, 122641245], 261: [790116096, 137225779, 682962673, 899018674, 508776302, 122641245], 262: [790116096, 137225779, 682962673, 899018674, 508776302, 122641245], 263: [790116096, 137225779, 682962673, 899018674, 508776302, 122641245], 264: [790116096, 137225779, 682962673, 899018674, 508776302, 122641245], 265: [572008657, 462363856, 73572149, 373295410, 71342224, 588158464], 266: [572008657, 462363856, 73572149, 373295410, 71342224, 588158464], 267: [572008657, 462363856, 73572149, 373295410, 71342224, 588158464], 268: [572008657, 462363856, 73572149, 373295410, 71342224, 588158464], 269: [572008657, 462363856, 73572149, 373295410, 71342224, 588158464], 270: [304518462, 515898375, 851004156, 534834967, 432242968, 502241841], 271: [304518462, 515898375, 851004156, 534834967, 432242968, 502241841], 272: [304518462, 515898375, 851004156, 534834967, 432242968, 502241841], 273: [304518462, 515898375, 851004156, 534834967, 432242968, 502241841], 274: [304518462, 515898375, 851004156, 534834967, 432242968, 502241841], 275: [37028267, 569432894, 628436154, 696374524, 793143712, 416325218], 276: [37028267, 569432894, 628436154, 696374524, 793143712, 416325218], 277: [37028267, 569432894, 628436154, 696374524, 793143712, 416325218], 278: [37028267, 569432894, 628436154, 696374524, 793143712, 416325218], 279: [37028267, 569432894, 628436154, 696374524, 793143712, 416325218], 280: [720155325, 351363855, 792690674, 545176893, 952379269, 778974762], 281: [720155325,
351363855, 792690674, 545176893, 952379269, 778974762], 282: [720155325, 351363855, 792690674, 545176893, 952379269, 778974762], 283: [720155325, 351363855, 792690674, 545176893, 952379269, 778974762], 284: [720155325, 351363855, 792690674, 545176893, 952379269, 778974762], 285: [403282374, 133294816, 956945194, 393979262, 111614817, 141624297], 286: [403282374, 133294816, 956945194, 393979262, 111614817, 141624297], 287: [403282374, 133294816, 956945194, 393979262, 111614817, 141624297], 288: [403282374, 133294816, 956945194, 393979262, 111614817, 141624297], 289: [403282374, 133294816, 956945194, 393979262, 111614817, 141624297], 290: [37026667, 643622228, 508022227, 930044452, 69185187, 952840008], 291: [37026667, 643622228, 508022227, 930044452, 69185187, 952840008], 292: [37026667, 643622228, 508022227, 930044452, 69185187, 952840008], 293: [37026667, 643622228, 508022227, 930044452, 69185187, 952840008], 294: [37026667, 643622228, 508022227, 930044452, 69185187, 952840008], 295: [670770969, 153949631, 59099260, 466109633, 26755557, 764055710], 296: [670770969, 153949631, 59099260, 466109633, 26755557, 764055710], 297: [670770969, 153949631, 59099260, 466109633, 26755557, 764055710], 298: [670770969, 153949631, 59099260, 466109633, 26755557, 764055710], 299: [670770969, 153949631, 59099260, 466109633, 26755557, 764055710], 300: [905338260, 326830077, 885886823, 915776600, 675663711, 431245307], 301: [905338260, 326830077, 885886823, 915776600, 675663711, 431245307], 302: [905338260, 326830077, 885886823, 915776600, 675663711, 431245307], 303: [905338260, 326830077, 885886823, 915776600, 675663711, 431245307], 304: [905338260, 326830077, 885886823, 915776600, 675663711, 431245307], 305: [139905542, 499710523, 712674377, 365443558, 324571856, 98434904], 306: [139905542, 499710523, 712674377, 365443558, 324571856, 98434904], 307: [139905542, 499710523, 712674377, 365443558, 324571856, 98434904], 308: [139905542, 499710523, 712674377, 365443558, 324571856, 98434904], 309: [139905542, 499710523, 712674377, 365443558, 324571856, 98434904], 310: [975295831, 335144003, 815172452, 728712302, 664817785, 621598405], 311: [975295831, 335144003, 815172452, 728712302, 664817785, 621598405], 312: [975295831, 335144003, 815172452, 728712302, 664817785, 621598405], 313: [975295831, 335144003, 815172452, 728712302, 664817785, 621598405], 314: [975295831, 335144003, 815172452, 728712302, 664817785, 621598405], 315: [810686111, 170577483, 917670527, 91981037, 5063705, 144761897], 316: [810686111, 170577483, 917670527, 91981037, 5063705, 144761897], 317: [810686111, 170577483, 917670527, 91981037, 5063705, 144761897], 318: [810686111, 170577483, 917670527, 91981037, 5063705, 144761897], 319: [810686111, 170577483, 917670527, 91981037, 5063705, 144761897], 320: [246899380, 668564006, 295879114, 368851558, 36647409, 523899293], 321: [246899380, 668564006, 295879114, 368851558, 36647409, 523899293], 322: [246899380, 668564006, 295879114, 368851558, 36647409, 523899293], 323: [246899380, 668564006, 295879114, 368851558, 36647409, 523899293], 324: [246899380, 668564006, 295879114, 368851558, 36647409, 523899293], 325: [683112658, 166550520, 674087710, 645722079, 68231113, 903036689], 326: [683112658, 166550520, 674087710, 645722079, 68231113, 903036689], 327: [683112658, 166550520, 674087710, 645722079, 68231113, 903036689], 328: [683112658, 166550520, 674087710, 645722079, 68231113, 903036689], 329: [683112658, 166550520, 674087710, 645722079, 68231113, 903036689], 330: [720148925, 327090077, 328006818, 836194377, 791152601, 138147971], 331: [720148925, 327090077, 328006818, 836194377, 791152601, 138147971], 332: [720148925, 327090077, 328006818, 836194377, 791152601, 138147971], 333: [720148925, 327090077, 328006818, 836194377, 791152601, 138147971], 334: [720148925, 327090077, 328006818, 836194377, 791152601, 138147971], 335: [757185192, 487629634, 981925935, 26666666, 514074080, 373259262], 336: [757185192, 487629634, 981925935, 26666666, 514074080, 373259262], 337: [757185192, 487629634, 981925935, 26666666, 514074080, 373259262], 338: [757185192, 487629634, 981925935, 26666666, 514074080, 373259262], 339: [757185192, 487629634, 981925935, 26666666, 514074080, 373259262], 340: [395044448, 310722225, 911555564, 130740741, 928333343, 464344448], 341: [395044448, 310722225, 911555564, 130740741, 928333343, 464344448], 342: [395044448, 310722225, 911555564, 130740741, 928333343, 464344448], 343: [395044448, 310722225, 911555564, 130740741, 928333343, 464344448], 344: [395044448, 310722225, 911555564, 130740741, 928333343, 464344448], 345: [32903704, 133814816, 841185193, 234814816, 342592597, 555429634], 346: [32903704, 133814816, 841185193, 234814816, 342592597, 555429634], 347: [32903704, 133814816, 841185193, 234814816, 342592597, 555429634], 348: [32903704, 133814816, 841185193, 234814816, 342592597, 555429634], 349: [32903704, 133814816, 841185193, 234814816, 342592597, 555429634], 350: [921791712, 553617042, 935413342, 478829633, 341192597, 909896452], 351: [921791712, 553617042, 935413342, 478829633, 341192597, 909896452], 352: [921791712, 553617042, 935413342, 478829633, 341192597, 909896452], 353: [921791712, 553617042, 935413342, 478829633, 341192597, 909896452], 354: [921791712, 553617042, 935413342, 478829633, 341192597, 909896452], 355: [810679711, 973419268, 29641482, 722844450, 339792597, 264363261], 356: [810679711, 973419268, 29641482, 722844450, 339792597, 264363261], 357: [810679711, 973419268, 29641482, 722844450, 339792597, 264363261], 358: [810679711, 973419268, 29641482, 722844450, 339792597, 264363261], 359: [810679711, 973419268, 29641482, 722844450, 339792597, 264363261], 360: [950596453, 989931120, 288468151, 106800000, 922733343, 882211711], 361: [950596453, 989931120, 288468151, 106800000, 922733343, 882211711], 362: [950596453, 989931120, 288468151, 106800000, 922733343, 882211711], 363: [950596453, 989931120, 288468151, 106800000, 922733343, 882211711], 364: [950596453, 989931120, 288468151, 106800000, 922733343, 882211711], 365: [90513186, 6442963, 547294820, 490755559, 505674080, 500060152], 366: [90513186, 6442963, 547294820, 490755559, 505674080, 500060152], 367: [90513186, 6442963, 547294820, 490755559, 505674080, 500060152], 368: [90513186, 6442963, 547294820, 490755559, 505674080, 500060152], 369: [90513186, 6442963, 547294820, 490755559, 505674080, 500060152], 370: [481458671, 619664450, 970720009,
14651851, 672955563, 381290225], 371: [481458671, 619664450, 970720009, 14651851, 672955563, 381290225], 372: [481458671, 619664450, 970720009, 14651851, 672955563, 381290225], 373: [481458671, 619664450, 970720009, 14651851, 672955563, 381290225], 374: [481458671, 619664450, 970720009, 14651851, 672955563, 381290225], 375: [872404156, 232885928, 394145189, 538548152, 840237046, 262520298], 376: [872404156,
232885928, 394145189, 538548152, 840237046, 262520298], 377: [872404156, 232885928, 394145189, 538548152, 840237046, 262520298], 378: [872404156, 232885928, 394145189, 538548152, 840237046, 262520298], 379: [872404156, 232885928, 394145189, 538548152, 840237046, 262520298], 380: [514378375, 442817041, 982168898, 202385186, 591859266, 407132003], 381: [514378375, 442817041, 982168898, 202385186, 591859266, 407132003], 382: [514378375, 442817041, 982168898, 202385186, 591859266, 407132003], 383: [514378375, 442817041, 982168898, 202385186, 591859266, 407132003], 384: [514378375, 442817041, 982168898, 202385186, 591859266, 407132003], 385: [156352594, 652748154, 570192598, 866222229, 343481486, 551743708], 386: [156352594, 652748154, 570192598, 866222229, 343481486, 551743708], 387: [156352594, 652748154, 570192598, 866222229, 343481486, 551743708], 388: [156352594, 652748154, 570192598, 866222229, 343481486, 551743708], 389: [156352594, 652748154, 570192598, 866222229, 343481486, 551743708], 390: [49355556, 459388893, 322814818, 670000005, 679444452, 959737045], 391: [49355556, 459388893, 322814818, 670000005, 679444452, 959737045], 392: [49355556, 459388893, 322814818, 670000005, 679444452, 959737045], 393: [49355556, 459388893, 322814818, 670000005, 679444452, 959737045], 394: [49355556, 459388893, 322814818, 670000005, 679444452, 959737045], 395:
[942358527, 266029632, 75437038, 473777781, 15407409, 367730373], 396: [942358527, 266029632, 75437038, 473777781, 15407409, 367730373],
397: [942358527, 266029632, 75437038, 473777781, 15407409, 367730373], 398: [942358527, 266029632, 75437038, 473777781, 15407409, 367730373], 399: [942358527, 266029632, 75437038, 473777781, 15407409, 367730373], 400: [399147411, 978022231, 758088896, 141777778, 392500005,
471204448], 401: [399147411, 978022231, 758088896, 141777778, 392500005, 471204448], 402: [399147411, 978022231, 758088896, 141777778, 392500005, 471204448], 403: [399147411, 978022231, 758088896, 141777778, 392500005, 471204448], 404: [399147411, 978022231, 758088896, 141777778, 392500005, 471204448], 405: [855936304, 690014821, 440740745, 809777784, 769592601, 574678523], 406: [855936304, 690014821, 440740745, 809777784, 769592601, 574678523], 407: [855936304, 690014821, 440740745, 809777784, 769592601, 574678523], 408: [855936304, 690014821, 440740745, 809777784, 769592601, 574678523], 409: [855936304, 690014821, 440740745, 809777784, 769592601, 574678523], 410: [876511119, 307359262, 53422223, 342000002, 187814818, 373633336], 411: [876511119, 307359262, 53422223, 342000002, 187814818, 373633336], 412: [876511119, 307359262, 53422223, 342000002, 187814818, 373633336], 413: [876511119, 307359262, 53422223, 342000002, 187814818, 373633336], 414: [876511119, 307359262, 53422223, 342000002, 187814818, 373633336], 415: [897085934, 924703712, 666103710, 874222229, 606037044, 172588149], 416: [897085934, 924703712, 666103710, 874222229, 606037044, 172588149], 417: [897085934, 924703712, 666103710, 874222229, 606037044, 172588149], 418: [897085934, 924703712, 666103710, 874222229, 606037044, 172588149], 419: [897085934, 924703712, 666103710, 874222229, 606037044, 172588149], 420: [481446671, 447400004, 208814817, 270666668, 65388891, 667023709], 421: [481446671, 447400004, 208814817, 270666668, 65388891, 667023709], 422: [481446671, 447400004, 208814817, 270666668, 65388891, 667023709], 423: [481446671, 447400004, 208814817, 270666668, 65388891, 667023709], 424: [481446671, 447400004, 208814817, 270666668, 65388891, 667023709], 425: [65807408, 970096305,
751525933, 667111116, 524740747, 161459260], 426: [65807408, 970096305, 751525933, 667111116, 524740747, 161459260], 427: [65807408, 970096305, 751525933, 667111116, 524740747, 161459260], 428: [65807408, 970096305, 751525933, 667111116, 524740747, 161459260], 429: [65807408, 970096305, 751525933, 667111116, 524740747, 161459260], 430: [213954076, 398144448, 224266669, 927777785, 25222224, 351375558], 431: [213954076, 398144448, 224266669, 927777785, 25222224, 351375558], 432: [213954076, 398144448, 224266669, 927777785, 25222224, 351375558], 433: [213954076, 398144448, 224266669, 927777785, 25222224, 351375558], 434: [213954076, 398144448, 224266669, 927777785, 25222224, 351375558], 435: [362100744, 826192600, 697007414, 188444445, 525703710, 541291856], 436: [362100744, 826192600, 697007414, 188444445, 525703710, 541291856], 437: [362100744, 826192600, 697007414, 188444445, 525703710, 541291856], 438: [362100744, 826192600, 697007414, 188444445, 525703710, 541291856], 439: [362100744, 826192600, 697007414, 188444445, 525703710, 541291856], 440: [74033334, 159592594, 99777779, 313333335, 67314817, 426688892], 441: [74033334, 159592594, 99777779, 313333335, 67314817, 426688892], 442: [74033334, 159592594, 99777779, 313333335, 67314817, 426688892], 443: [74033334, 159592594, 99777779, 313333335, 67314817, 426688892], 444: [74033334, 159592594, 99777779, 313333335, 67314817, 426688892], 445: [785965933, 492992597, 502548153, 438222225, 608925933, 312085928], 446: [785965933, 492992597, 502548153, 438222225, 608925933, 312085928], 447: [785965933, 492992597, 502548153, 438222225, 608925933, 312085928], 448: [785965933,
492992597, 502548153, 438222225, 608925933, 312085928], 449: [785965933, 492992597, 502548153, 438222225, 608925933, 312085928], 450: [374441633, 40386667, 600779265, 151614815, 648455563, 325062817], 451: [374441633, 40386667, 600779265, 151614815, 648455563, 325062817], 452: [374441633, 40386667, 600779265, 151614815, 648455563, 325062817], 453: [374441633, 40386667, 600779265, 151614815, 648455563, 325062817], 454: [374441633, 40386667, 600779265, 151614815, 648455563, 325062817], 455: [962917342, 587780746, 699010377, 865007414, 687985193, 338039706], 456: [962917342, 587780746, 699010377, 865007414, 687985193, 338039706], 457: [962917342, 587780746, 699010377, 865007414,
687985193, 338039706], 458: [962917342, 587780746, 699010377, 865007414, 687985193, 338039706], 459: [962917342, 587780746, 699010377, 865007414, 687985193, 338039706], 460: [427936152, 349168892, 492702227, 166903704, 225433337, 478596448], 461: [427936152, 349168892, 492702227, 166903704, 225433337, 478596448], 462: [427936152, 349168892, 492702227, 166903704, 225433337, 478596448], 463: [427936152, 349168892, 492702227, 166903704, 225433337, 478596448], 464: [427936152, 349168892, 492702227, 166903704, 225433337, 478596448], 465: [892954971, 110557038, 286394077, 468800003, 762881490, 619153190], 466: [892954971, 110557038, 286394077, 468800003, 762881490, 619153190], 467:
[892954971, 110557038, 286394077, 468800003, 762881490, 619153190], 468: [892954971, 110557038, 286394077, 468800003, 762881490, 619153190], 469: [892954971, 110557038, 286394077, 468800003, 762881490, 619153190], 470: [234516891, 85939260, 775546674, 359200002, 798248157,
887289785], 471: [234516891, 85939260, 775546674, 359200002, 798248157, 887289785], 472: [234516891, 85939260, 775546674, 359200002, 798248157, 887289785], 473: [234516891, 85939260, 775546674, 359200002, 798248157, 887289785], 474: [234516891, 85939260, 775546674, 359200002, 798248157, 887289785], 475: [576078820, 61321482, 264699262, 249600001, 833614824, 155426371], 476: [576078820, 61321482, 264699262, 249600001, 833614824, 155426371], 477: [576078820, 61321482, 264699262, 249600001, 833614824, 155426371], 478: [576078820, 61321482, 264699262, 249600001, 833614824, 155426371], 479: [576078820, 61321482, 264699262, 249600001, 833614824, 155426371], 480: [794183859, 250697780, 449312597, 728503709, 366900005, 551142819], 481: [794183859, 250697780, 449312597, 728503709, 366900005, 551142819], 482: [794183859, 250697780, 449312597, 728503709, 366900005, 551142819], 483: [794183859, 250697780, 449312597, 728503709, 366900005, 551142819], 484: [794183859, 250697780, 449312597, 728503709, 366900005, 551142819], 485: [12288889, 440074078, 633925932, 207407408, 900185195, 946859267], 486: [12288889, 440074078, 633925932, 207407408, 900185195, 946859267], 487: [12288889, 440074078, 633925932, 207407408, 900185195, 946859267], 488: [12288889, 440074078, 633925932, 207407408, 900185195, 946859267], 489: [12288889, 440074078, 633925932, 207407408, 900185195, 946859267], 490: [106937038, 843444452, 514000005, 274814816, 931388899, 470155559], 491: [106937038, 843444452, 514000005, 274814816, 931388899, 470155559], 492: [106937038, 843444452, 514000005, 274814816, 931388899, 470155559], 493: [106937038, 843444452, 514000005, 274814816, 931388899, 470155559], 494: [106937038, 843444452, 514000005, 274814816, 931388899, 470155559], 495: [201585187, 246814817, 394074078, 342222224, 962592603, 993451860], 496: [201585187, 246814817, 394074078, 342222224, 962592603, 993451860], 497: [201585187, 246814817, 394074078, 342222224, 962592603, 993451860], 498: [201585187, 246814817, 394074078, 342222224, 962592603, 993451860], 499: [201585187, 246814817, 394074078, 342222224, 962592603, 993451860]}
for r in range(500):
lst=LI[r]
LI[r]=Lagrange_Interpolation(lst=lst,x0=r,xd=500,mod=mod)
T=int(readline())
for _ in range(T):
M=int(readline())
r=M%500
ans=LI[r][M]
print(ans)
LI={r:LI[r].coefficient for r in range(500)}