← 返回题目列表

AtCoder · codefestival_2016_final_f

F. 王者之路

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

分数: 1000 点

问题陈述

有 N 高桥王国的城镇。它们方便地编号 1 通过 N.

高桥王计划巡视 M 天。他将确定一系列城镇 c,并参观城镇 c_i 上 i第一天。也就是说,在 i- 第天,他将从当前位置前往城镇 c_i。如果他已经在城里了 c_i,他将留在那个城镇。他在旅行开始前的位置是城镇 1,首都。行程在小镇结束 c_M,没有回首都。

问题是这个王国没有平坦的道路。他决定通过在旅行时亲自铺路来解决这个问题。当他从城镇出发时 a 到镇 b,将有一条新铺设的来自城镇的单向道路 a 到镇 b.

由于他关心他的人民,他希望在他的旅行结束后满足以下条件:“可以通过他铺好的道路从任何一个城镇前往任何另一个城镇”。有多少个城镇序列 c 满足这个条件吗?

约束

  • 2≦N≦300
  • 1≦M≦300

输入

输入由标准输入按以下格式给出:

N M

输出

打印满足条件的城镇序列的数量,模 1000000007 (=10^9+7).


示例输入 1

3 3

示例输出 1

2

如下所示,只有当 c = (2,3,1) or c = (3,2,1)。序列如 c = (2,3,2), c = (2,1,3), c = (1,2,2) 不满足条件。


示例输入 2

150 300

示例输出 2

734286322

示例输入 3

300 150

示例输出 3

0