結果

問題 No.42 貯金箱の溜息
ユーザー vwxyz
提出日時 2021-08-21 08:11:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0