1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std; 

int main(){
    int n, k; cin>>n>>k; 
    long long A[n+1]; 
    A[0] = 1; 
    A[1] = 0; 
    A[2] = (long long)k; 
    int mod = 1000000007; 

    for (int i = 3; i <= n; i++){
        A[i] = (A[i-1]*k)%mod + (A[i-2]*(k-1))%mod; 
        A[i] %= mod; 
    }

    cout<<A[n]<<endl; 
}