You are given a string $S$ of length $N$. You are also given an integer $K$. The string consists of digits from $1-9$ only. Determine the number of ways to partition the string $S$ such that each segment value is less than $K$.

If there is no way to perform partition on the string, then print $0$.

Since the answer could be a large, print the answer as $10^9+7$.

Input format

• First line: of input contains a single integer T denoting the number of test cases.
• For each test case:
  • First line: Two space-separated integers $N$ and $K$
  • Second line: A string $S$ of size $N$ 

Output format

Print the required answer. 

Constraints

$1\le T\le 5\\ 1\le N\le 10^5\\ 1\le K\le 10^{18}$