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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def abc(i,n,w,x,c):\n if c==n:\n  return x==w\n ans=0\n for j in range(10):\n  ans+=abc(j,n,w,x+j-i,c+1)\n return ans\ne=10**9+7\nt=int(input())\nfor _ in range(t):\n n,w=list(map(int,input().split()))\n ans=0\n for i in range(1,10):\n  pass\n  #ans+=abc(i,n,w,0,1)\n #print(ans)\n if n==1:\n  if w==0:\n   print(9)\n  else:\n   print(0)\n else:\n  if w>=9:\n   print(0)\n  elif w>0:\n   x = ((9-w)*pow(10,n-2,e))%e\n   print(x)\n  elif w<=-10:\n   print(0)\n  elif w==0:\n   print((9*pow(10,n-2,e))%e)\n  else:\n   c = -w\n   x=((10-c)*pow(10,n-2,e))%e\n   print(x)\n \n  \n0\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13497