考虑组合数学。

前缀芝士：

1、$A^n_m$ = $n*(n-1)*(n-2)*...*(n-m+1)$.

2、$C^n_m$ = $n*(n-1)*(n-2)*...*(n-m+1) / m!$。

阅读题面不难看出，如果在不考虑合不合法的情况下，共有$C^n_m$种可能。

发现很难直接算出不合法个数，于是考虑下面这个式子: 不合法方案数 = 总方案数 - 合法方案数。

于是，问题就转成了求出总共的合法方案数(dp党勿扰):

假设这个长为$m$的式子第一个数为$x$，那么接下来的第二个数就有$(m-1)$种可能，以此类推，除了第一个数字以外，其他的每一个数字都有$(m-1)$种可能。

合法方案数：

$(m-1)^m / (m-1) * m$

那么不合法方案数(ans)：

$C^n_m - (m-1)^m / (m-1) * m$

但是100%的数据范围n，m有10^18,用普通的单重循环肯定会超时。因此考虑快速幂(不懂得自行bdfs，简单来讲就是将十进制数转成二进制数，再处理每一位）。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum = 1,sum2,n,m,x,y;
const int MOD = 1e9 + 7;//定义一个模数
inline ll read() {//快读+快输，可自行改成cin或scanf
	ll x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * m;
}
inline void write(ll x) {
	if(x < 0) {
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
signed main() {
	m = read(), n = read();//这里的读入是反的
	m %= MOD;//先预处理
	x = m  y = n;//第一次快速幂处理总方案数
	while(y) {//快速幂模板，下同(洛谷P1226)，x和y相当于x^y
		if(y & 1) sum = sum * x % MOD;//边计算边取模
		x = x % MOD * x % MOD;
		y >>= 1;//等价于y=y/2
	}
	sum2 = m % MOD;
	x = (m - 1 + MOD) % MOD, y = n - 1;//计算不合法方案数，但是因为y要转成二进制，所以不可以取模！！！
	while(y){
		if(y & 1) sum2 = sum2 * x % MOD;
		x = x % MOD * x % MOD;
		y >>= 1;
	}
	write((sum  + MOD - sum2) % MOD);//计算不合法方案数，但是可能会变成负数，所以可以先加上一个模数再进行取模
	return 0;//完结撒花！
}