레이팅 미적용Petar and Ivana are bored during a long winter afternoon, so they decided to
invent a game with numbers.
Petar takes a sheet of paper and randomly writes down \(n\) numbers. Each number
is chosen completely at random and independently among the integers from
1 to \(k\). Using this procedure, Petar creates an array \(a\) of \(n\) numbers.
Ivana says that she especially likes some arrays because they have a “hidden
balance”, and she calls them structures. An array is a structure if the following
conditions are satisfied:
• Every number from 1 to \(n\) appears in the array exactly once.
• For every index \(i\) (\(1 \le i \le n\)), it holds that |\(a_{i} + i - n - 1\)| ≤1.
Ivana is interested in the probability that Petar, choosing the numbers completely at random, constructs
an array that is a structure.
It can be proven that the answer can always be represented as a fraction ^{P}
_{Q}^{,} ^{where} ^{P} ^{is} ^{an} ^{integer} ^{and} ^{Q}
is a positive integer not divisible by \(10^{9} + 7\). In that case, output \(P \cdot Q^{−1}\) (mod \(10^{9} + 7\)).
The first line contains the natural numbers \(n\) and \(k\) (\(1 \le n\), \(k \le 10^{9}\)), the numbers from the problem
statement.
Output a single number, the answer to the question from the problem statement.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 17점 | n, \(k \le 7\) |
2 | 23점 | \(n \le 7\), \(k \le 100\) |
3 | 19점 | \(n \le 20\), \(k \le 100\) |
4 | 25점 | n, \(k \le 10^{6}\) |
5 | 26점 | No additional constraints. |
2 102 25000000047 94100976822Clarification of the second example: The arrays a that Petar can construct are: (1, 1), (1, 2), (2, 1),
(2, 2). The arrays that are structures are (1, 2) and (2, 1). The probability that Petar completely at
random obtains an array that is a structure is 2
4, i.e. 500000004 (mod 109 + 7).