A squarer is a simple and convenient device. You give it some positive integer X and it calculates its square.
Leha is implementing a module of this device which is responsible for squaring the numbers consisting of multiple repetitions of one digit. But it turned out that it's not as simple as he thought.
Please help him now!

-----Input-----
The first line contains one integer T denoting the number of testcases. The descriptions of T test cases follow.
Each of the following T lines contain 2 space-separated integers - N and D, respectively. It means that the number X in the corresponding testcase consists of the digit D repeated N times (in decimal representation).

-----Output-----
As the answer can be very large, we ask you to output its hash which is computed in the following way:
Let's consider the integer answer Y as a 0-indexed array starting from its leftmost digit. The hash function is calculated as:
p0*Y[0] + p1*Y[1] + ... + pM-1*Y[M-1] modulo 109 + 7 
where M is the length of the array representation of Y and p equals 23.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ D ≤ 9
- Subtask 1 (16 points): 1 ≤ N ≤ 9
- Subtask 2 (25 points): 1 ≤ N ≤ 100
- Subtask 3 (27 points): 1 ≤ N ≤ 2 × 104
- Subtask 4 (32 points): 1 ≤ N ≤ 106

-----Example-----
Input:3
1 4
3 6
3 5

Output:139
40079781
32745632

-----Explanation-----
In the first test case, X = 4 and Y = 16. Its hash equals 1*1 + 23*6 = 139.

Difficulty: interview

Starter code:

Solutions:
val = 10**9 + 7
def MOD(a,b):
 aans = a
 ans = 1
 while b>0:
  ans = (ans*aans)%val
  aans = (aans*aans)%val
  b/=2
 return ans%val
 


for i in range(eval(input())):    
 n,d= list(map(int,input().split()))
 a=int(str(d)*n)
 sqr = str(a*a)
 ans =0
 count=0
 for ii in sqr :
  ans= ans+int(ii)*23**count
  count+=1
  z=int(ii)*ans
 print(ans % (10**9+7))
 
  


T=int(input())
while(T>0):
 [N,D]=list(map(int,input('').split()))
 carry=0
 cal=0
 ans=''
 i=1
 k=0
 while i<=N:
  ans+= str(chr(((carry+i)%10)+ord('0')))
  carry=int((carry+i)/10)
  cal+=1
  i+=1
  k+=1
 #print ans
 i-=2
 while i>=1:
  ans+= str(chr(((carry+i)%10)+ord('0')))
  carry=int((carry+i)/10)
  cal+=1
  i-=1
  k+=1
 #print ans
 while carry>0:
  ans+= str((((carry+i)%10)+ord('0')))
  carry=int((carry)/10)
  cal+=1
  k+=1
 #print ans[0:k]
 #print long(ans)
 ans = int(ans)
 ans*=(D*D)
 ans=str(ans)
 #print ans
 
 length=len(ans)
 ans1=0
 p=1
 for i in range(length):
  ans1=((ord(ans[i])-ord('0'))*p+ans1)%1000000007
  p=(p*23)%1000000007
 print(ans1)

 T-=1

tts=[1,23]
mod=10**9+7
for x in range(2,2*10**6+1):
 tts.append(tts[x-1]*23%mod)

t=eval(input())
while t>0:
 n,d=list(map(int,input().split()))
 num=int(str(d)*n)
 num**=2
 res=0
 i=0
 for x in str(num):
  res+=((int(x)*tts[i]))
  i+=1
 print(res%mod)
 t-=1


def show(n,d):
 t=0
 m=1000000007
 for i in range(0,n):
  t=t*10+d


 t=t*t
 st=str(t)
 s=0
 for i in range(0,len(st)):
  s=(s+((23**i)*int(st[i]))% m)% m
 print(s)

def main():
 t=int(input())
 while t>0:
  n,d=input().split()
  n=int(n)
  d=int(d)
  show(n,d)
  t-=1

main()




test=eval(input())


while test>0:

 test=test-1
 N, D = list(map(int, input().strip().split()))
 number=""
 for i in range(N):
  number=number+str(D)
 num=int(number)
 sq=num*num
 z=str(sq)
 l=len(z)
 
 ans=0
 for i in range (l):
  ans=ans+(int(z[i])*(23**(i)))
  ans=ans%1000000007
 print(ans)

def main():
 mod=(10**9+7)
 for i in range(eval(input())):
  printk =0
  c=0
  A,D= list(map(int,input().split()))
  aks=int(str(D)*A)
  s=(aks*aks)
  hey=str(s)
  for ii in hey:
   printk= printk+int(ii)*23**c
   __=int(ii)*printk
   c+=1
   #print __
   #print c
  ok_=printk % mod 
  print(ok_)
main() 


test=int(input())
for i in range(0,test):
 n,k=list(map(int,input().split()))
 l=str(k)*n
 l=int(l)
 k=l*l
 u=str(k).strip()
 t=len(u)
 j=1
 ans=0
 for h in range(0,t):
  ans = ans+((int(u[h])%1000000007)*(j%1000000007)%1000000007)%1000000007
  j=(23*j)%1000000007
 print(ans%1000000007)

T=int(input())
while(T>0):
 [N,D]=list(map(int,input('').split()))
 carry=0
 cal=0
 ans=0
 i=1
 while i<=N:
  ans=((carry+i)%10)*(10**cal)+ans
  carry=int((carry+i)/10)
  cal+=1
  i+=1
 #print ans
 i-=2
 while i>=1:
  ans=((carry+i)%10)*(10**cal)+ans
  carry=int((carry+i)/10)
  cal+=1
  i-=1
 #print ans
 while carry>0:
  ans=((carry)%10)*(10**cal)+ans
  carry=int((carry)/10)
  cal+=1
 #print ans
 ans*=(D*D)
 ans=str(ans)
 #print ans
 
 length=len(ans)
 ans1=0
 p=1
 for i in range(length):
  ans1=((ord(ans[i])-ord('0'))*p+ans1)%1000000007
  p=(p*23)%1000000007
 print(ans1)
 T-=1

test=int(input())
for i in range(0,test):
 n,k=list(map(int,input().split()))
 l=str(k)*n
 l=int(l)
 k=l*l
 u=str(k).strip()
 t=len(u)
 j=1
 ans=0
 for h in range(0,t):
  ans = ans+((int(u[h])%1000000007)*(j%1000000007)%1000000007)%1000000007
  j=(23*j)%1000000007
 print(ans%1000000007)

test=eval(input())


while test>0:

 test=test-1
 N, D = list(map(int, input().strip().split()))
 number=0
 for i in range(N):
  number=number+D*(10**i)
 sq=number*number
 z=str(sq)
 l=len(z)
 
 ans=0
 for i in range (l):
  ans=ans+(int(z[i])*(23**(i)))
  ans=ans%1000000007
 print(ans)

mod=1000000007
dp =[]
dp.append(1)
tens=[]
tens.append(10)
tws=[]
tws.append(1)
for i in range(1, 21):
 tens.append(tens[i-1]*tens[i-1])
 dp.append(dp[i-1]*tens[i-1]+dp[i-1])
 tws.append(tws[i-1]*2) 

t=eval(input())
t=int(t)
for i in range(0, t):
 now=0
 b, a = input().split()
 a=int(a)
 b=int(b)
 j=20
 val=0
 while(j>=0):
  if(b>=tws[j]):
   val*=tens[j]
   val+=dp[j]
   b-=tws[j]
  j-=1
 val*=a
 act=val*val
 now=str(act)
 # print(now)
 dow=1
 ans=0
 for c in now:
  x=int(c)
  # print(x)
  # print(dow)
  ans+=(dow*x)
  dow*=23
  dow%=mod
  ans%=mod
 print(ans)
 # digs=[]
 # while(act >0):
 #   d=act%10
 #   digs.append(d)
 #   act=act/10
 # now=0
 # while (act > 0):
 #   d=act%10
 #   now*=10
 #   now+=d
 #   act=act/10
 # count=0
 # ans=0
 # mul=1
 # while (now > 0):
 #   d=now%10
 #   ans+=(mul*d)
 #   ans%=mod
 #   now/=10
 #   count+=1
 #   mul*=23
 #   mul%=mod
 # print(ans)





from math import *
t=int(input())
for i in range(0,t):
 a,b=input().split()
 a,b=int(a),int(b)
 c=""
 for j in range(1,a+1):
  c+=str(j)
 for j in range(1,a):
  c+=str(a-j)
 c=int(c)
 b*=b
 c=c*b
 c=str(c)
 mod=10**9+7
 ans=0
 for j in range(0,len(c)):
  ans+=(((23**j)%mod)*(int(c[j])%mod))%mod
 ans=ans%mod
 print(ans)


MOD = 10**9+7
tcase = eval(input())
for times in range(tcase):
 rep, digit = list(map(int,input().split()))
 number = str(int(str(digit)*rep)**2)
 mult = 1
 ans = 0
 for dig in number:
  ans += ((int(dig)%MOD)*mult)%MOD
  mult = ((mult%MOD)*23)%MOD
 print(ans%MOD)

from math import *
t=int(input())
for i in range(0,t):
 a,b=input().split()
 a,b=int(a),str(b)
 c=""
 for j in range(0,a):
  c+=b
 c=int(c)
 c=c**2
 c=str(c)
 mod=10**9+7
 ans=0
 for j in range(0,len(c)):
  ans+=(((23**j)%mod)*(int(c[j])%mod))%mod
 ans=ans%mod
 print(ans)


def square(n,d):
 if n==1:
  return d*d
 a=""
 for i in range(1,n+1):
  a=a+str(i)
 for i in range(n-1,0,-1):
  a=a+str(i)
 #print a
 return d*d*int(a)

t=eval(input())
p=23
parray=[]
parray.append(1)
for i in range(1,3240001):
 parray.append((parray[i-1]*p)%1000000007)
for x in range(0,t):
 n,d=list(map(int,input().split()))
 '''
    num=int(str(d)*n)
    sq=num**2
    '''
 sq=square(n,d)
 #print "this is a test %d"%sq
 m=len(str(sq))
 #print "length of square = %d"%m
 i=0
 sum=0
 sqArray=list(map(int,list(str(sq))))
 #print sqArray
 while i<m:
  #print "i = %d"%i
  sum = (sum+(sqArray[m-i-1])*(parray[m-i-1]))%1000000007
  i=i+1
 print("%d" %sum)

import math
import string
MOD = pow(10, 9) + 7
p=23
MAX = 2*pow(10, 6) + 10
P={}
P[0]=1
for q in range(1, MAX):
 P[q] = (P[q-1]*p)%MOD
for _ in range(int(input())):
 n, d = list(map(int, input().split()))
 number = [(d)]*(n)
 C=[0]*(n+n)
 s=len(C)-1
 for j in range(n-1, -1, -1):
  carry = 0
  shift = s
  for i in range(n-1, -1, -1):
   m = number[i]*number[j]
   summ = m+C[shift]+carry
   num = summ%10
   c = summ/10
   C[shift] = num
   carry = c
   shift-=1
  C[shift] = C[shift] + carry
  s-=1
 jump = 0
 for i in range(len(C)):
  if C[i]==0:
   jump+=1
  else:
   break
 C=C[jump:]
 ans=0
 for i in range(len(C)):
  ans+=(P[i]*int(C[i]))%MOD
 print(ans%MOD)

test = eval(input())
while test:
 test =test-1
 n,d = list(map(int,input().split()))
 num=0
 for i in range(n):
  num=num*10+d
 sqr=num**2
 s=sqr.__str__()
 l=len(s)
 ans=0
 for i in range(l):
  ans=(ans+((23**i)*int(s[i])))%1000000007
 print(ans)



import sys

f = sys.stdin

if len(sys.argv) > 1:
 f = open(sys.argv[1], "rt")

T = int(f.readline().strip())

MOD = 10**9 + 7

def calc(N, D):
 X = [D] * N

 X_d = [0] * N # X * D
 carry = 0
 for i in range(N):
  val = D * D + carry
  X_d[i] = val % 10
  carry = val // 10
 assert carry < 10
 X_d.append(carry) # Could be 0, still use for convenience.

 product = [0] * (2*N)
 #~ print(X_d)
 #~ print(product)

 # (1)
 carry = 0
 cur_sum = 0
 for i in range(N):
  cur_sum += X_d[i]
  val = cur_sum + carry
  product[i] = val % 10
  carry = val // 10

 # (2)
 cur_sum += X_d[N]
 for i in range(N):
  cur_sum -= X_d[i]
  val = cur_sum + carry
  product[N+i] = val % 10
  carry = val // 10

 # (3)
 while carry > 0:
  product.append(carry % 10)
  carry = carry // 10

 while product and product[-1] == 0:
  del product[-1]

 h = 0
 for x in product:
  h = (h * 23 + x ) % MOD

 return h

for case_id in range(1, T+1):
 N, D = list(map(int, f.readline().strip().split()))

 r = calc(N, D)

 print(r)


import math
import string
MOD = pow(10, 9) + 7
p=23
for _ in range(int(input())):
 n, d = list(map(int, input().split()))
 number = [(d)]*(n)
 C=[0]*(n+n)
 s=len(C)-1
 for j in range(n-1, -1, -1):
  carry = 0
  shift = s
  for i in range(n-1, -1, -1):
   m = number[i]*number[j]
   summ = m+C[shift]+carry
   num = summ%10
   c = summ/10
   C[shift] = num
   carry = c
   shift-=1
  C[shift] = C[shift] + carry
  s-=1
 jump = 0
 for i in range(len(C)):
  if C[i]==0:
   jump+=1
  else:
   break
 C=C[jump:]
 ans=0
 for i in range(len(C)):
  ans+=(pow(p, i, MOD)*int(C[i]))%MOD
 print(ans%MOD)

import sys

mod = 10**9 + 7;

l = [1]

for i in range(1,(10**6)+1):
 l.append((l[-1]*23)%mod)

def solve(num):
 length = len(num)
 ans = 0
 for i in range(length):
  ans += l[i] * int(num[i])
  ans %= mod
 return ans



for cases in range(int(sys.stdin.readline())):
 n,d = list(map(int,sys.stdin.readline().split()))
 num = int((str(d)*n))%mod
 num = num**2
 print(solve(str(num)))