← 返回题目列表

AtCoder · tenka1_2015_qualA_e

E. 天下一巫师

中文机器翻译题面 查看原题

問題文

你正在练习在地上画魔法阵,以成为世界上最好的魔法师。魔法阵的绘制方法如下。

  • 在圆周上 N 等间隔点, 绘制时使 1 位于正北。
  • 用线段连接点,K 绘制一些在其顶点之外没有自交点的多边形。
  • 每个点恰好是 1 必须包含在一个多边形内。
  • 绘制的多边形必须连接。然而,当多边形连接时,所有多边形对都被连接。 对于 (a, b) ,多边形 a 和多边形 指的是 b 是串联的状态。还有,多边形 a 和多边形 指的是 b 满足以下任一条件时连接。
    • 多角形 a 边和多边形 b 一侧是 1 相交于多个点。
    • 多角形 a 和多边形 指的是 c 是相连且多边形的 b 和多边形 指的是 c 连接的多边形 当 c 存在。

例如,N = 10, K = 3 时,你可以画一个如下所示的魔法阵。

fig1

像下面这样的魔法阵不是正确的魔法阵,因为多边形没有连接。

fig2

你决定计算一下有多少个魔法阵可以用这种方式绘制。


入力

输入是按以下格式从标准输入给出的。

N K
  • 1 行上,2 整数 N (3 ≦ N ≦ 400), K (3 ≦ K ≦ N) 用空格分隔。

出力

计算使用问题陈述中的方法可以绘制的魔法阵数量。 除了上述之外,如果所有满足 1,000,000,007 (10^9+7) 后的余数 1 行输出。在输出末尾插入换行符。

配点

针对此问题设置了部分分数。

  • N ≦ 50 和 N/3 < K 的测试用例都得到正确回答,30 点。 如果您正确回答了所有满足
  • N ≦ 50 的测试用例都被正确回答, 50 点。 如果您正确回答了所有满足
  • 如果所有测试用例都回答正确,除上述之外, 50 点。 如果您正确回答了所有满足

入力例1

6 3

出力例1

8

下面 8 你可以在街上画一个魔法阵。

fig3

入力例2

6 4

出力例2

1

只能绘制六边形图案。


入力例3

50 5

出力例3

665400552