class Solution{
    public:
    typedef long long ll;

    long long countWays(int n, ll k){

        vector<ll> dp(n + 1);
        dp[1] = k;
        dp[2] = (k * k);
        const ll MOD = 1e9 + 7;
        for(int i = 3; i <= n; i++) {
            dp[i] = (((dp[i - 1] + dp[i - 2]) % MOD) * ((k - 1) % MOD)) % MOD;
        }
        return dp[n] % MOD;
    }
};