VK gave a problem to Chef, but Chef is too lazy, so he asked you to solve the problem for him. The statement of the problem follows.
Consider an integer with $N$ digits (in decimal notation, without leading zeroes) $D_1, D_2, D_3, \dots, D_N$. Here, $D_1$ is the most significant digit and $D_N$ the least significant. The weight of this integer is defined as ∑i=2N(Di−Di−1).∑i=2N(Di−Di−1).\sum_{i=2}^N (D_i - D_{i-1})\,.
You are given integers $N$ and $W$. Find the number of positive integers with $N$ digits (without leading zeroes) and weight equal to $W$. Compute this number modulo $10^9+7$.
-----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 two space-separated integers $N$ and $W$ denoting the number of digits and the required weight.
-----Output-----
For each test case, print a single line containing one integer — the number of $N$-digit positive integers with weight $W$, modulo $10^9+7$.
-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le N \le 10^{18}$
- $|W| \le 300$
-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 10^3$
- $2 \le N \le 10^3$
Subtask #2 (80 points): original constraints
-----Example Input-----
1
2 3
-----Example Output-----
6
-----Explanation-----
Example case 1: Remember that the digits are arranged from most significant to least significant as $D_1, D_2$. The two-digit integers with weight $3$ are $14, 25, 36, 47, 58, 69$. For example, the weight of $14$ is $D_2-D_1 = 4-1 = 3$. We can see that there are no other possible numbers.
# Python3 program to find total possible 
# numbers with n digits and weight w 

# Function to find total possible 
# numbers with n digits and weight w 
def findNumbers(n, w): 

 x = 0; 
 s = 0; 

 # When Weight of an integer 
 # is Positive 
 if (w >= 0 and w <= 8): 
  # Subtract the weight from 9 
  x = 9 - w; 
 
 # When weight of an integer 
 # is negative 
 elif (w >= -9 and w <= -1): 
  
  # add the weight to 10 to 
  # make it positive 
  x = 10 + w; 
 
 s = pow(10, n - 2); 
 s = (x * s); 
 
 return s; 

# Driver code 

# number of digits in an 
# integer and w as weight 


# This code is contributed 
# by mits
m = 10**9 + 7
for _ in range(int(input())):
 n,w = list(map(int,input().split()))
 print(findNumbers(n,w)%m)

# Python3 program to find total possible 
# numbers with n digits and weight w 

# Function to find total possible 
# numbers with n digits and weight w 
def findNumbers(n, w): 

 x = 0; 
 s = 0; 

 # When Weight of an integer 
 # is Positive 
 if (w >= 0 and w <= 8): 
  # Subtract the weight from 9 
  x = 9 - w; 
 
 # When weight of an integer 
 # is negative 
 elif (w >= -9 and w <= -1): 
  
  # add the weight to 10 to 
  # make it positive 
  x = 10 + w; 
 
 s = pow(10, n - 2); 
 s = (x * s); 
 
 return s; 

# Driver code 

# number of digits in an 
# integer and w as weight 


# This code is contributed 
# by mits
m = 10**9 + 7
for _ in range(int(input())):
 n,w = list(map(int,input().split()))
 print(findNumbers(n,w)%m)
