题解 | #小红的新周赛#

E

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fios ofstream out("test.txt");cout.rdbuf(out.rdbuf())
#define endl "\n"
#define lowbit(x) (x & (-x))
#define INF 0x3f3f3f3f
#define MINF 2147483647
#define eps 1e-6
#define PI acos(-1)
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
#define int long long
const int N = 1010, mod = 1e9 + 7;
int n, k;

int quick_mi(int m, int k)
{
    int res = 1, t = m;
    while(k)
    {
        if(k & 1) res = res * t % mod;
        t = t * t % mod;
        k >>= 1;
    }
    return res;
}

signed main()
{
    cin >> n >> k;

    int even = k / 2, odd = k - even;

    int res = 0;

    res += quick_mi(even, n);
    res += quick_mi(even, n / 3) * quick_mi(odd, n - n / 3) % mod;
    res += quick_mi(even, (n + 2) / 3)  * quick_mi(odd, n - (n + 2) / 3) % mod;
    res += quick_mi(even, (n + 1) / 3)  * quick_mi(odd, n - (n + 1) / 3) % mod;

    cout << res % mod << endl;

    return 0;
}