题目描述

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

输入

第一行两个整数$n,m$。

输出

仅一个整数表示答案$\bmod 10^9+7$。

输入样例

2 2

输出样例

4

提示

【数据规模】 对于30%的数据，$n≤5，m≤10$； 对于60%的数据，$n≤80，m≤3000$； 对于100%的数据，$1≤n≤10000，1≤m≤50000$。

图的计数说明

要求1到n存在路径，且最短路至少n-1条边；无路不计入。平行边按有序端点对的重数区分图，不给各平行边额外编号。n=2,m=2样例的4种图为两条1→2，或一条1→2分别搭配1自环、2自环、2→1，明确排除了不可达图和边的排列顺序。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。