Problem

Given an array $B$ of $N$ integer elements and an integer $X$. We have to assign value to elements of an array $A$ of size $N + 1$.

It is given that $A[0] = X$.

Array $B$ follows the given property:

• $B[0] = 0$.
• $B[i] = 1$.

We have to assign value to each array element in array $A$ for $1 \leq i \leq N$ such that:

• The maximum possible value assigned is $X$.
• The value assigned to any array element must be positive.
• The value assigned to the element at index $i$ is less than or equal to the value assigned to the element at index $B[i]$, i.e., $A[i] \leq A[B[i]]$.

Find the number of valid assignments possible modulo $10^9 + 7$.

It is guaranteed that the value of array $B$ is such that there does not exist any pair of indices $(i,j)$ in array $A$ such that both conditions hold simultaneously:

• Value assigned to element at index $i$ i.e. $A[i]$ is less than or equal to value assigned to element at index $j$ i.e. $A[j]$.
• Value assigned to element at index $j$ i.e. $A[j]$ is less than or equal to value assigned to element at index $i$ i.e. $A[i]$.

Input

• $T$: Number of test cases
• $N$: Size of array $B$
• $X$: Maximum possible value
• $B$: Array $B$ of $N$ integer elements

Output

• The number of valid assignments possible modulo $10^9 + 7$