凸多边形正则划分问题:对于给定的 n 和 k,求一个凸 nk−2(n−1) 边形的 k 角剖分的方案数,对 109+7 取模。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含两个整数 n,k。
输出格式
输出一行一个整数,表示所有询问的答案之和。
样例数据
样例输入
2 3
3 3
3 4
样例输出
19
子任务
对于 50% 的数据,n≤5000。
对于 100% 的数据,k≤200,n≤1100000
注
- 赛时并未提供数据组数,“请选手自行评估”。
- 赛时并未提供 k 的下界,且出题人答疑时声称并不保证(
尽管数据里没有)k≰。 - 赛时并未提供空间限制,
“请选手自行评估”QOJ 上设置为 1 GB。