有個玩著頂級手機遊戲的人,某天在試圖簽署合約時,對自己必須玩的遊戲非常生氣。遊戲規則如下:
- 有一個牌池,包含編號從 $1$ 到 $2N+K$ 的牌。
- 遊戲會從這個牌池逐張抽出 $N$ 張牌,抽出後不放回,也就是同一個數字不能抽到兩次。
- 抽出牌後,玩家會猜測下一張牌的數字較大還是較小。
讓玩家生氣的是,由於運氣不好,小數字後總是出現更小的數字,大數字後總是出現更大的數字。因此,玩家希望修改遊戲的隨機機制來避免這種情況。他的修改為抽牌增加了以下兩條規則:
- 若抽到編號從 $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 \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$,第二張牌有 $3$ 種不同的可能;若第一張牌為 $3$,第二張牌有 $4$ 種不同的可能。因此,修改後的遊戲共有 $16$ 種可能。$\frac{16}{20}=\frac45$。這個機率在我們的模數下等於 $600000005$。
範例評測程式
範例評測程式預期每個案例採用以下格式:
$$N\ K$$
若所要求的函式成功回傳一個整數,評測程式會以下列格式印出結果 $R$:
$$R$$