Minimum Bubble Operations

You are given a permutation (or a circular permutation) A of the set \({1,2,\dots,n}\) (the indices of the values are from 1 to \(n\)). For a permutation, A is represented as \([A_1,A_2,\dots,A_n]\). For a circular permutation, the array is considered in a circle so that the predecessor of the first element is the last element.

Define \(f(A)\) as the minimum number of operations needed to sort \(A\) into ascending order. The ascending order is defined as follows:

• For a permutation, \(A\) is sorted if and only if for every \(2\le i\le n\), the element \(A[i]\) is exactly \(A[i-1]+1\). In other words, the sorted permutation is \([1,2,\dots,n]\).
• For a circular permutation, \(A\) is sorted if and only if when viewed in a circle, for every consecutive pair \(x, x+1\) (taking \(n+1\) as 1), the element \(x+1\) immediately follows \(x\) in the circle. Equivalently, every circularly sorted permutation is just a cyclic shift of \([1,2,\dots,n]\). Note that in the circle the predecessor of the first element is the \(n\)th element.

An operation is defined as follows. In one operation, you can choose any one element in \(A\) and perform one or more bubble steps. One bubble step is defined as: if the chosen element is less than its immediate left neighbor (in the circular sense, for a permutation the left neighbor of \(A_1\) does not exist, while for a circular permutation the left neighbor of \(A_1\) is \(A_n\)), then swap it with that neighbor. You may continue bubbling the same element consecutively until a bubble step is not possible (at which point the current operation stops immediately). Note that you may choose to perform fewer bubble steps than the maximum possible in that operation.

For example, consider the permutation \([3,5,2,1,4]\). You can choose the element \(1\) and bubble it. You may stop after one, two, or three bubble steps, possibly obtaining one of the arrays:

• After one bubble: \([3,5,1,2,4]\)
• After two bubbles: \([3,1,5,2,4]\)
• After three bubbles: \([1,3,5,2,4]\)

For a circular permutation, e.g. \([2,1,4,3]\), if you choose the element \(1\) (which is at index 2), since in a circle the predecessor of the first element is the last, you can obtain one of:

• \([1,2,4,3]\)
• \([3,2,4,1]\)
• \([3,2,1,4]\)

It can be shown that the optimal strategy yields \(f(A) = d\), where:

[ \begin{aligned} \text{For a permutation: } & d = #{x\in{1,2,\dots,n-1} : \text{the position of }x+1 \text{ is less than the position of } x}, \ \text{For a circular permutation: } & d = #{x\in{1,2,\dots,n} : \text{if we define } \text{pos}(n+1)=\text{pos}(1), \text{ then } \text{pos}(x+1) < \text{pos}(x)}. \end{aligned} ]

Given three integers \(n\), \(k\) and \(type\) (either 1 or 2), you are to compute:

• If \(type=1\): the number of permutations \(A\) of length \(n\) for which \(f(A)=k\).
• If \(type=2\): the number of circular permutations \(A\) of length \(n\) for which \(f(A)=k\).

Since the answer can be very large, output it modulo \(10^9+7\.

---

Hint: For the permutation case, it turns out that \(f(A)\) is exactly the number of indices \(x\) (from 1 to \(n-1\)) such that the position of \(x+1\) is less than the position of \(x\). The number of permutations of \(n\) having exactly \(d\) such "descents" is given by the Eulerian number \(A(n,d)\). For the circular case, one can prove that the answer is \(n\times A(n-1,k-1)\) (note that for any circular permutation, \(f(A)\ge 1\)).

inputFormat

The first and only line of input contains three integers \(n\), \(k\) and \(type\) separated by spaces.

• \(1 \le n \le 500\) (you may assume the constraints are small enough for an \(O(n^2)\) solution)
• For \(type = 1\), \(0 \le k \le n-1\).
• For \(type = 2\), \(1 \le k \le n\) (note that in a circular permutation \(f(A)\) is at least 1).

outputFormat

Output a single integer: the number of permutations (if \(type=1\)) or circular permutations (if \(type=2\)) \(A\) of length \(n\) with \(f(A)=k\), taken modulo \(10^9+7\).

sample

3 0 1

1