当前没有测试数据。

图的计数

题目描述

询问有多少个包含$n$个点$m$条边的有向图，从$1$号点到达$n$号点需要经过至少$n-1$条边。该有向图中可以包含重边和自环。

答案对$10^{9}+7$取模。

输入格式

一行两个整数$n$，$m$。

输出格式

仅一个整数，表示答案。

数据范围与提示

• 对于$30\%$的数据，$n \leq 5$，$m \leq 10$；
• 对于$60\%$的数据，$n \leq 80$，$m \leq 3000$；
• 对于$100\%$的数据，$1 \leq n \leq 10^{4}$，$1 \leq m \leq 5 \times 10^{4}$。

样例

2 2

4

9999 15000

916298491