Problem Description

Given a permutation or circular permutation \( A \) with indices and value range from \( 1 \) to \( n \), define \( f(A) \) as the minimum number of operations required to sort \( A \) in ascending order.

In each operation, you can choose an element and perform multiple bubbles. A single bubble is defined as: if the element is smaller than the previous element, you can swap it with the previous element. The operation stops immediately if no more bubbles can be performed. Otherwise, you can perform bubbles consecutively any number of times.

For example, given the permutation \([3, 5, 2, 1, 4]\), an operation can choose element \(1\) to get permutations \([3, 5, 1, 2, 4]\), \([3, 1, 5, 2, 4]\), or \([1, 3, 5, 2, 4]\).

For a circular permutation \([2, 1, 4, 3]\), choosing element \(1\) can result in circular permutations \([1, 2, 4, 3]\), \([3, 2, 4, 1]\), or \([3, 2, 1, 4]\). Note that in a circular permutation, the previous element of the first element is the \(n\)-th element.

A permutation or circular permutation is sorted in ascending 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\), and \(type\), you need to:
- When \(type = 1\), find the number of length-\(n\) permutations \(A\) such that \(f(A) = k\).
- When \(type = 2\), find the number of length-\(n\) circular permutations \(A\) such that \(f(A) = k\).

The answer should be taken modulo \(10^9 + 7\).

Input Format

Input consists of three positive integers \(n\), \(k\), and \(type\) on a single line, as described in the problem statement.

Output Format

Output a single integer, which is the answer modulo \(10^9 + 7\).

Sample Input and Output

Sample Input #1

4 2 1

Sample Output #1

11

Sample Input #2

5 2 2

Sample Output #2

14

Sample Input #3

50 10 1

Sample Output #3

808620624

Sample Input #4

50 10 2

Sample Output #4

578144115

Notes/Hints

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]\) as the same circular permutation. Two circular permutations are considered different if and only if there exists an \(i\) (where \(2 \leq i \leq n\)) such that the previous element of element \(i\) is different in the two circular permutations.

Data Range

For all data, \(1 \leq k < n \leq 500\), \(1 \leq type \leq 2\).

见题面 Input 部分

见题面 Output 部分