GrandPaPa in Buhăiești Tired of going by train with the godfather, Little IR12660 decided to go for the next best thing: going with the Grandpapa. He soon started regretting his decision after the Grandpapa started telling him stories of his youth. One of them was how he got to solve the following:
You are given integers $$$n$$$, $$$m$$$, and an array $$$B$$$ of length $$$n$$$ with values in the range $$$[0, m]$$$.
Determine the number of ways to construct an array $$$A$$$ of length $$$n$$$, such that:
- $$$0 \le A[i] \le m$$$
- $$$\text{mex}(A[1 \dots i]) \leq \text{mex}(B[1 \dots i])$$$ for every $$$1 \leq i \leq n$$$.
- $$$A$$$ is lexicographically smaller than $$$B$$$.
Here, $$$\text{mex}$$$ (minimum excluded value) of a set of integers is defined as the smallest non-negative integer that is not present in the set. For example:
- $$$\text{mex}(\{0, 1, 3\}) = 2$$$
- $$$\text{mex}(\{1, 2, 3\}) = 0$$$
The notation $$$\text{mex}(A[1 \dots i])$$$ refers to the $$$\text{mex}$$$ of the elements $$$A[1], A[2], \dots, A[i]$$$.
Little IR12660 didn't pay much attention to Grandpapa's solution, so now he has to make his own. But of course, he will ask you to solve it instead of trying on his own powers.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$) — the number of test cases.
Each test case consists of:
- A single line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 50$$$).
- A second line containing $$$n$$$ integers — the array $$$B$$$ ($$$0 \leq B[i] \leq m$$$).
It is guaranteed that the sum of $$$n$$$ does not exceed $$$50$$$ and the sum of $$$m$$$ does not exceed $$$50$$$.
For each test case, output a single integer — the number of valid arrays $$$A$$$ satisfying the conditions modulo $$$10^9+7$$$.
83 22 1 24 31 0 2 32 11 15 43 0 1 2 46 21 2 1 0 2 29 32 1 0 3 2 1 3 2 01 002 22 2
5 11 0 1089 62 52856 0 3
For the first testcase, the possible arrays $$$A$$$ are:
- $$$[1,2,2]$$$
- $$$[1,1,2]$$$
- $$$[1,1,1]$$$
- $$$[1,2,1]$$$
- $$$[2,1,1]$$$
