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
#include <iostream>   

using namespace std;
typedef long long ll;

const ll my_m = 1e9 + 7;
const int rozmiar = 3e3 + 7;

ll tab[rozmiar][2];


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n, m;

    cin >> n >> m; // drzewa , gatunki
    
    
    tab[1][0] = m;
    tab[1][1] = 0;
    for (int i = 2; i <= n; i++)
    {
        tab[i][0] = ((tab[i - 1][0] * m) % my_m + tab[i - 1][1])%my_m;
        tab[i][1] = (tab[i - 1][0]) % my_m;
        
    }

    /*cout << tab[1][0] << "\n";
    cout << tab[2][0] << "\n";
    cout << tab[3][0] << "\n";
    cout << tab[4][0] << "\n";
    cout << "T:\n";
    cout << tab[1][1] << "\n";
    cout << tab[2][1] << "\n";
    cout << tab[3][1] << "\n";
    cout << tab[4][1] << "\n";*/
    cout << tab[n][1] << "\n";

    
    return 0;
}