On her way to ChefLand, Marichka noticed $10^K$ road signs (numbered $0$ through $10^K - 1$). For each valid $i$, the sign with number $i$ had the integer $i$ written on one side and $10^K-i-1$ written on the other side.
Now, Marichka is wondering — how many road signs have exactly two distinct decimal digits written on them (on both sides in total)? Since this number may be large, compute it modulo $10^9+7$.
For example, if $K = 3$, the two integers written on the road sign $363$ are $363$ and $636$, and they contain two distinct digits $3$ and $6$, but on the road sign $362$, there are integers $362$ and $637$, which contain four distinct digits — $2$, $3$, $6$ and $7$. On the road sign $11$, there are integers $11$ and $988$, which contain three distinct digits — $1$, $9$ and $8$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $K$.

-----Output-----
For each test case, print a single line containing one integer — the number of road signs with exactly two digits, modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le K \le 10^9$

-----Subtasks-----
Subtask #1 (20 points): $1 \le T, K \le 5$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
1

-----Example Output-----
10

Difficulty: interview

Starter code:

Solutions:
import math
t=int(input())
for i in range(t):
    k=int(input())
    res=((pow(2,k,1000000007))*5)%1000000007
    print(res)

import math
t=int(input())
for i in range(t):
    k=int(input())
    res=((pow(2,k,1000000007))*5)
    print(res)

t=int(input())
for i in range(t):
    k=int(input())
    res=((pow(2,k))*5)%1000000007
    print(res)

__author__ = 'Prateek'


def test():
    k = int(input())
    ans = (pow(2,k-1,int(10**9+7))*10)%(int(10**9+7))
    print(ans)


if __author__ == 'Prateek':
    t = int(input())
    for _ in range(t):
        test()


from sys import stdin,stdout


def power(x, y, p): 

    res = 1; # Initialize result 

  

    # Update x if it is  

    # more than or equal to p 

    x = x % p;  

  

    while (y > 0):  

          

        # If y is odd, multiply 

        # x with the result 

        if (y & 1): 

            res = (res * x) % p; 

  

        # y must be even now 

        y = y >> 1; # y = y/2 

        x = (x * x) % p; 

          

    return res; 

 
def sin():
    return stdin.readline()

def out(s):
    stdout.write(str(s)+"\n")
    	
m=1000000007
for i in range(int(input())):
    n=sin()[:-1]
    remainderB = 0; 
    for i in range(len(n)):
        remainderB = ((remainderB * 10 + 

                   ord(n[i]) - 48) % 

                   (m - 1)); 
    out((power(2, remainderB, m)*5)%m); 

from sys import stdin,stdout

def sin():
    return stdin.readline()

def out(s):
    stdout.write(str(s)+"\n")
    	
m=1000000007
for i in range(int(input())):
    n=int(sin())
    print(((2**n)*5)%m)

from sys import stdin,stdout
inn=stdin.readline
out=stdout.write
for i in range(int(inn())):
    n=int(inn());m=10**9+7
    v=(10*pow(2,n-1,m))%m
    out(str(v)+'\n')

from sys import stdin,stdout
inn=stdin.readline
out=stdout.write
for i in range(int(inn())):
    n=int(inn());m=10**9+7
    for i in range(1,n+1):
        v=(10*pow(2,n-1,m))%m
    out(str(v)+'\n')

def power(val, p, mod):
    ans = 1
    while p:
        if p & 1:
            ans = ans * val % mod
        val = val * val % mod
        p >>= 1
    return ans;
t = int(input())
for i in range(t):
    k = int(input())
    print(10 * power(2, k-1, 1000000007) % 1000000007)

t = int(input())
def power(a, n):
    if n==0:
        return 1
    elif n==1:
        return a
    else:
        r = power(a, n//2)
        if n%2==0:
            return r*r
        else:
            return r*a*r
for i in range(t):
    k = int(input())
    print(10*(power(2,(k-1))))

t = int(input())
def power(a, n):
    ans = 1
    for i in range(n):
        ans*=a
    return ans
for i in range(t):
    k = int(input())
    print(10*(power(2,(k-1))))

t = int(input())
for i in range(t):
    k = int(input())
    print(10*(pow(2,(k-1))))

t = int(input())
for i in range(t):
    k = int(input())
    print(10*(2**(k-1)))

# cook your dish here
t = int(input())
for _ in range (t):
    K = int(input())
    K -= 1
    A = 2
    B = 10
    M = 10**9 + 7
    while K > 0:
        if K % 2 != 0:
            B = (B*A) % M
            K -= 1
        else:
            A = (A**2) % M
            K //= 2
    print(B)


# cook your dish here
t = int(input())
for _ in range(t):
    K = int(input())
    K -= 1
    A = 2
    B = 10
    M = 10**9 + 7
    while K > 0:
        if K % 2 != 0:
            B = (B*A) % M
            K -= 1
        else:
            A = (A**2) % M
            K //= 2
    print(B)


for i in range(int(input())):
    n=int(input())
    m=10**9+7
    for i in range(1,n+1):
        v=(10*(2**(n-1)))%m
    print(v)

for i in range(int(input())):
    n=int(input())
    m=10**9+7
    print(10*(2**(n-1))%m)

# cook your dish here
import math

def com():
    a=[]
    p=10
    m=1000000007
    a.append(10)
    for i in range(1,10):
        p=a[i-1]%m
        p=(p*2)%m
        p=p%m
        a.append(p)
    
    return a
        

t=int(input())
m=1000000007
while(t>0):
    k=int(input())
    c=2**(k-1)
    c=c%m
    c=c*10 
    c=c%m
    print(c)
    t-=1
	    


# cook your dish here
import math

def com():
    a=[]
    a.append(1)
    m=1000000007
    for i in range(1,1000000):
        p=a[i-1]%m
        p=p*2
        p=p%m
        a.append(p)
    return a
    
    
t=int(input())
a=com()
w=10000000-1
m=1000000007
while(t>0):
    k=int(input())
    c=a[k-1]*10 
    c=c%m
    c=int(c)
    print(c)
    t-=1
	    

# cook your dish here
import math

def com():
    a=[]
    p=10
    m=1000000007
    a.append(10)
    for i in range(1,10):
        p=a[i-1]%m
        p=(p*2)%m
        p=p%m
        a.append(p)
    
    return a
        

t=int(input())
a=com()
while(t>0):
    k=int(input())
    c=a[k-1]
    print(c)
    t-=1
	    

# cook your dish here
import math

def com():
    a=[]
    p=10
    m=1000000007
    a.append(10)
    for i in range(1,100):
        p=a[i-1]%m
        p=(p*2)%m
        p=p%m
        a.append(p)
    
    return a
        

t=int(input())
a=com()
while(t>0):
    k=int(input())
    c=a[k-1]
    print(c)
    t-=1
	    

# cook your dish here
import math
t=int(input())
while(t>0):
    k=int(input())
    j=0
    h=math.pow(10,k)-1
    h=int(h)
    c=0
    for i in range(h+1):
        ab=[]
        if(i==0):
            if(i not in ab):
                ab.append(i)
            p=h-i
            while(p>0):
                g=p%10
                if(g not in ab):
                    ab.append(g)
                p=p//10
        elif(i==h):
            if(i not in ab):
                ab.append(h-i)
            p=i
            while(p>0):
                g=p%10
                if(g not in ab):
                    ab.append(g)
                p=p//10
                
        else:
            p=i
            while(p>0):
                g=p%10
                if (g not in ab):
                    ab.append(g)
                p=p//10
            p=h-i
            while(p>0):
                g=p%10
                if(g not in ab):
                    ab.append(g)
                p=p//10
        if(len(ab)==2):
            c+=1
    print(c)
    t-=1
	    

# author: riyan

def bigpow(n, p, m):
    if p == 0:
        return 1
    elif p == 1:
        return n
    elif p % 2 == 0:
        tmp = bigpow(n, p // 2, m)
        return ((tmp * tmp) % m)
    else:
        return ((n * (bigpow(n, p - 1, m) % m)) % m)
    

def __starting_point():
    tc = int(input().strip())

    for t in range(tc):
        k = int(input().strip())
     
        m = int(1e9 + 7)
        ans = (10 * bigpow(2, k - 1, m)) % m

        print(ans)
            

__starting_point()

# author: riyan


def __starting_point():
    tc = int(input().strip())

    for t in range(tc):
        k = int(input().strip())

        ans = 10
        mod = int(1e9 + 7)
        for i in range(1, k):
            ans = (2 * (ans % mod)) % mod

        print(ans)
            

__starting_point()