1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

constexpr int mod = 1e9+7;

long long qp(long long a, long long b){
	long long res = 1;
	while(b){
		if(b&1) res *= a;
		a *= a;
		if(a >= mod) a %= mod;
		if(res >= mod) res %= mod;
		
		b>>=1;
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	long long res = 0, n, m;
	
	cin >> n >> m;
	
	if(n == 1) res = 0;
	else if(n == 2) res = m;
	else if(n == 3){
		res = qp(m, 2);
		if(res >= mod) res %= mod;
	}
	else if(n == 4){
		res = qp(m, 3) + qp(m, 2) - m;
		if(res >= mod) res %= mod;
	}
	else if(n == 5){
		res = qp(m, 4) + 2*qp(m, 3) - 2*qp(m, 2);
		if(res >= mod) res %= mod;
	}
	else if(n == 6){
		res = qp(m, 5) + 3*qp(m, 4) - 2*qp(m, 3) - 4*qp(m, 2) + 3*m;
		if(res >= mod) res %= mod;		
	}
	else if(n == 7){
		res = qp(m, 6) + 4*qp(m, 5) - qp(m, 4) - 12*qp(m, 3) + 9*qp(m, 2);
		if(res >= mod) res %= mod;
	}
	else if(n == 8){
		res = qp(m, 7) + 5*qp(m, 6) + qp(m, 5) - 23*qp(m, 4) + 7*qp(m, 3) + 27*qp(m, 2) - 17*m;
		if(res >= mod) res %= mod;
	}
	else if(n == 9){
		res = qp(m, 8) + 6*qp(m, 7) + 4*qp(m, 6) - 36*qp(m, 5) - 14*qp(m, 4) + 108*qp(m, 3) - 68*qp(m, 2);		
		if(res >= mod) res %= mod;
	}
	else if(n == 10){
		res = qp(m, 9) + 7*qp(m, 8) + 8*qp(m, 7) - 50*qp(m, 6) - 64*qp(m, 5) + 244*qp(m, 4) - 22*qp(m, 3) - 278*qp(m, 2) + 155*m;				
		if(res >= mod) res %= mod;
	}
	else res = 2137;
	
	cout << res << '\n';
	
	return 0;
}