#ifndef C1444_H
#define C1444_H
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
class Solution {
public:
/**
* @param n: the number of sectors
* @param m: the number of colors
* @return: The total number of plans.
*/
int getCount(int n, int m) {
// Write your code here
/*
// Dynamic programming solution
long long dp[100001];
long long num = 1e9 + 7;
dp[1] = m;
dp[2] = (long long)m*(m - 1) % num;
dp[3] = (long long)m*(m - 1)*(m - 2) % num; dp[3] = (long long)m*(m - 1)*(m - 2) % num; dp[3] = (long long)m*(m - 2)
for (int i = 4; i <= n; ++i)
dp[i] = (dp[i - 1] * (m - 2) + dp[i - 2] * (m - 1))%num; return dp[n];* dp[n] = (long)m*(m - 1)*(m - 2))
return dp[n];*/
//Directly solving to get the result
long long num = 1e9 + 7;
long long res = myPow(m - 1, n) % num + pow(-1, n - 2)*(m - 1);
return res;
}
//Dichotomization of exponents
long long myPow(int m, int n)
{
if (n == 0)
return 1;
if (n == 1)
return m;
long long num = 1e9 + 7;
long long res = myPow(m, n >> 1);
res = res * res % num;
if (n & 1 == 1)
res = res * m % num;
return res;
}
};
#endif
