Problem Description

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 Format

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

Output Format

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

4 2 1

11

5 2 2

14

50 10 1

808620624

50 10 2

578144115

Hint

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

For all testdata, $1 \leq k < n \leq 500$ and $1 \leq type \leq 2$.

Translated by ChatGPT 5