凸多边形正则划分问题：对于给定的 $n$ 和 $k$，求一个凸 $nk-2(n-1)$ 边形的 $k$ 角剖分的方案数，对 $10^9+7$ 取模。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含两个整数 $n, k$。

输出格式

输出一行一个整数，表示所有询问的答案之和。

样例数据

样例输入

2 3
3 3
3 4

样例输出

19

子任务

对于 $50\%$ 的数据，$n \leq 5\,000$。

对于 $100\%$ 的数据，$k \leq 200, n \leq 1\,100\,000$

注

1. 赛时并未提供数据组数，“请选手自行评估”。
2. 赛时并未提供 $k$ 的下界，且出题人答疑时声称并不保证（尽管数据里没有）$k \nleq 2$。
3. 赛时并未提供空间限制，“请选手自行评估” QOJ 上设置为 1 GB。