제출 #19767

#제출 시각아이디문제언어결과실행 시간메모리
19767Qwaz괄호 (kriii4_R)C++14
100 / 100
137 ms1084 KiB
#include <cstdio> typedef long long ll; const int MOD = 1000000007; ll modpow(ll a, ll x) { ll ret = 1; a = a % MOD; while (x) { if (x & 1) ret = ret * a % MOD; a = a * a % MOD; x >>= 1; } return ret; } int main() { int n, k; scanf("%d%d", &n, &k); ll res = 1, catalan = 1, xk = 1; for (int i = 2; i <= n+1; i++) { if (i & 1) { res = res * (k+1) % MOD; } else { res = (res * (k+1) - catalan * xk) % MOD; if (res < 0) res += MOD; int t = (i >> 1) - 1; catalan = 2 * (2*t + 1) * modpow(t+2, MOD-2) % MOD * catalan % MOD; xk = xk * k % MOD; } } printf("%lld\n", res); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...