记录编号	616267	评测结果	AAAAAAAAAA
题目名称	4411.数列求和	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	3.884 s
提交时间	2026-06-04 20:32:15	内存使用	14.74 MiB

#include <iostream>
 
using namespace std;

const int K = 2026;

long long n;
long long a;
long long k;
long long P = 1e9 + 7;
long long choose[K][K];
long long cal[K];
long long res[K];

namespace Barrett_Reduction {
	__int128 I;
	long long ModNum;
	
	inline void init (long long mod) {
		I = ((__int128) 1 << 64) / mod;
		ModNum = mod;
	}
	
	inline long long mod (long long num) {
		return num - ((__int128(num) * I) >> 64) * ModNum;
	}
}

using namespace Barrett_Reduction;

inline long long quick_pow (long long x, long long y) {
    long long ans = 1;
    while (y) {
        if (y & 1) {
            ans = mod (ans * x);
        }
        x = mod (x * x);
        y >>= 1;
    }
    return ans;
}

void magic_cut (long long n) {
	if (n == 1) {
		for (int now_k = 0; now_k <= k; now_k++) {
			res[now_k] = a;
		}
		return;
	}
	
	long long m = n / 2;
	magic_cut (m);
	long long multi_m = quick_pow (a, m);
	m = mod (m);
	for (int now_k = 0; now_k <= k; now_k++) {
		long long base = 1;
		for (int j = 0; j <= now_k; j++) {
			cal[now_k] = mod (cal[now_k] + mod (mod (choose[now_k][j] * base) * res[now_k - j]));
			base = mod (base * m);
		}
		cal[now_k] = mod (mod (cal[now_k] * multi_m) + res[now_k]);
	}
	for (int now_k = 0; now_k <= k; now_k++) {
		res[now_k] = cal[now_k];
		cal[now_k] = 0;
	}
	
	if (n % 2) {
		for (int now_k = 0; now_k <= k; now_k++) {
			res[now_k] = mod (res[now_k] + mod (quick_pow (mod (n), now_k) * quick_pow (a, n)));
		}	
	}
}
 
int main () {
    
    #ifndef ONLINE_JUDGE
    freopen ("oeis.in", "r", stdin);
    freopen ("oeis.out", "w", stdout);
    #endif
    
    cin >> n >> a >> k >> P;
    
    init (P);
    
    for (int i = 0; i <= k; i++) {
    	choose[i][0] = 1;
    	for (int j = 1; j <= i; j++) {
    		choose[i][j] = mod (choose[i - 1][j] + choose[i - 1][j - 1]);
		}
	}
    
    magic_cut (n);
    
    cout << res[k] << endl;
    
    return 0;
}