最高峰のモバイルゲームを遊んでいるある人は、ある日、契約に署名しようとしているときに遊ばなければならないゲームにひどく腹を立てました。ゲームの内容は次のとおりです。
- $1$ から $2N+K$ までの数が書かれたカードの山があります。
- この山から $N$ 枚のカードを1枚ずつ引きます（引いたカードは戻しません。つまり、同じ数を2回引くことはありません）。
- カードを引いた後、プレイヤーは次のカードの数がそれより大きいか小さいかを予想します。
プレイヤーが腹を立てているのは、運が悪く、小さい数の後にはいつもさらに小さい数が、大きい数の後にはいつもさらに大きい数が出ることです。そこで、ゲームの乱数の仕組みを変更してこれを防ごうとします。その変更によって、カードの引き方に次の2つのルールを追加します。
- $1$ から $N$ までの数のカードを引いた場合、次に引くカードの数は $N$ より真に大きくなければなりません（$>N$）。
- $N+K+1$ から $2N+K$ までの数のカードを引いた場合、次に引くカードの数は $N+K+1$ より真に小さくなければなりません（$<N+K+1$）。
プレイヤーは、この変更によってゲームをどれほど壊してしまったか知りたいと思っています。その程度は、変更後のゲームで可能な異なるカード列の総数を、通常のゲームで可能なカード列の総数で割った比で測ります。この比を $10^9+7$ を法として求めてください。
実装の詳細
次の関数を実装してください。
int oyun(int N, int K)- $N$ と $K$ は、問題文で述べたカードの山と引くカードの枚数を決める整数です。
- この関数は、求める比を返してください。
- この関数は、各テストでちょうど1回呼び出されます。
制約
- $1\le N\le 10^6$
- $1\le K\le 100$
小課題
| 小課題 | 配点 | 追加の制約 | 依存関係 |
|---|---|---|---|
| 1 | 10 | $1\le N,K\le 6$ | — |
| 2 | 18 | $1\le N\le 100$ | 1 |
| 3 | 6 | $1\le N\le 1000$ | 1, 2 |
| 4 | 47 | $1\le N\le 10^4$ | 1, 2, 3 |
| 5 | 19 | 追加の制約はありません | 1, 2, 3, 4 |
入出力例
oyun(2, 1)
上の関数呼び出しは $600000005$ を返す必要があります。
数は $1,2,3,4,5$ です。2枚のカードを引きます。通常の場合、カードの引き方は20通りあります。変更後のゲームでは、最初のカードが $1$、$2$、$4$、$5$ のいずれかなら2枚目のカードには3通りの可能性があり、最初のカードが $3$ なら2枚目のカードには4通りの可能性があります。したがって、変更後のゲームには合計16通りの可能性があります。$\frac{16}{20}=\frac45$ です。この確率は、使用する法において $600000005$ に相当します。
サンプル採点プログラム
サンプル採点プログラムは、各ケースを次の形式で読み込みます。
$$N\ K$$
実装する関数が整数を正常に返した場合、その結果 $R$ を次の形式で出力します。
$$R$$