某位玩着顶尖手机游戏的人,有一天在试图签订合同时,对不得不玩的游戏非常生气。这个游戏的规则如下:
- 有一个牌池,其中的数字为 $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$$