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}\)