P8859 Bubble Sort.

There is a permutation or circular permutation $A$ whose values and indices are both in $1\sim n$. Define $f(A)$ as the minimum number of operations needed to sort $A$ in increasing order. In each operation, you may choose one element and **bubble** it forward (to the left) several times. One **bubble** is defined as follows: if this element is smaller than the previous element, you may swap it with the previous element. When it cannot **bubble** at some point, this operation stops immediately. Otherwise, it may **bubble** any number of times continuously. For example, given the permutation $[3,5,2,1,4]$, in one operation you can choose the element $1$ and obtain $[3,5,1,2,4]$, $[3,1,5,2,4]$, or $[1,3,5,2,4]$. For a circular permutation $[2,1,4,3]$, after choosing the element $1$ you can obtain the circular permutation $[1,2,4,3]$, $[3,2,4,1]$, or $[3,2,1,4]$. Note that in a circular permutation, the previous element of the $1$-st element is the $n$-th element. A permutation or circular permutation is sorted in increasing order if and only if for all $2 \leq i \leq n$, the previous element of element $i$ is element $i-1$. Given $n,k,type$, you need to: - When $type=1$, compute how many permutations $A$ of length $n$ satisfy $f(A)=k$. - When $type=2$, compute how many circular permutations $A$ of length $n$ satisfy $f(A)=k$. Output the answer modulo $10^9+7$.

Input one line with three positive integers $n,k,type$. Their meanings are described above.

Output one line with one integer, the answer modulo $10^9+7$.

#### Sample Explanation #1. The following permutations are valid: 1. $[1,4,2,3]$ 2. $[1,4,3,2]$ 3. $[2,1,4,3]$ 4. $[2,4,1,3]$ 5. $[2,4,3,1]$ 6. $[3,1,2,4]$ 7. $[3,1,4,2]$ 8. $[3,2,1,4]$ 9. $[3,2,4,1]$ 10. $[3,4,1,2]$ 11. $[3,4,2,1]$ #### Sample Explanation #2. The following circular permutations are valid: 1. $[1,2,5,3,4]$ 2. $[1,2,5,4,3]$ 3. $[1,3,2,5,4]$ 4. $[1,3,5,2,4]$ 5. $[1,3,5,4,2]$ 6. $[1,4,2,3,5]$ 7. $[1,4,2,5,3]$ 8. $[1,4,3,2,5]$ 9. $[1,4,3,5,2]$ 10. $[1,4,5,3,2]$ 11. $[1,5,2,4,3]$ 12. $[1,5,3,2,4]$ 13. $[1,5,3,4,2]$ 14. $[1,5,4,2,3]$ Note that we consider $[1,2,5,3,4]$ and $[2,5,3,4,1]$ to be the same circular permutation. That is, we consider two circular permutations to be different if and only if there exists some $2 \leq i \leq n$ such that the previous element of element $i$ is different in the two circular permutations. #### Constraints | Test Point ID | $n \leq$ | $k \leq$ | $type=$ | |:---------------:|:--------:|:--------:|:-------:| | $1 \sim 2$ | $7$ | $7$ | $1$ | | $3 \sim 4$ | $7$ | $7$ | $2$ | | $5 \sim 6$ | $15$ | $15$ | $1$ | | $7 \sim 8$ | $15$ | $15$ | $2$ | | $9 \sim 12$ | $50$ | $50$ | $1$ | | $13 \sim 16$ | $50$ | $50$ | $2$ | | $17$ | $500$ | $10$ | $1$ | | $18$ | $500$ | $10$ | $2$ | | $19$ | $500$ | $500$ | $1$ | | $20$ | $500$ | $500$ | $2$ | For all testdata, $1 \leq k < n \leq 500$ and $1 \leq type \leq 2$. Translated by ChatGPT 5