gawkmaster069 C
建立於 差異永不過期
import sys
import sys
def main():
input = sys.stdin.readline
input = sys.stdin.read
data = input().split()
def power(base, exp, P):
T = int(data[0])
res = 1
idx = 1
base %= P
for _ in range(T):
while exp > 0:
n = int(data[idx])
if exp & 1:
m = int(data[idx + 1])
res = (res * base) % P
p = int(data[idx + 2])
base = (base * base) % P
idx += 3
exp >>= 1
mm = m % p
return res
if mm == 0:
print(n % p)
def modInverse(n, P):
continue
return power(n, P - 2, P)
invm = pow(mm, p - 2, p)
C = [0] * (n + 1)
def solve():
C[0] = 1
N, M, P = map(int, input().split())
for i in range(1, n + 1):
invM = modInverse(M, P)
for j in range(i, 0, -1):
C[j] = (C[j] + C[j - 1]) % p
centers = []
ans = C[1] % p
for i in range(N):
invm_pow = 1
max_rad = min(i, N - 1 - i)
for k in range(1, n // 2 + 1):
centers.append((max_rad + 1, 1))
invm_pow = (invm_pow * invm) % p
for i in range(N - 1):
l_odd = 2 * k + 1
max_rad = min(i, N - 2 - i)
if l_odd <= n:
centers.append((max_rad + 1, invM))
ans = (ans + C[l_odd] * invm_pow % p) % p
l_even = 2 * k
globalSum = 0
if l_even <= n:
for cnt, start_prob in centers:
ans = (ans + C[l_even] * invm_pow % p) % p
if invM == 1:
print(ans)
term_sum = (cnt % P) * start_prob % P
if __name__ == "__main__":
else:
main()
num = (1 - power(invM, cnt, P) + P) % P
den = (1 - invM + P) % P
term_sum = start_prob * num % P * modInverse(den, P) % P
globalSum = (globalSum + term_sum) % P
ans = globalSum * globalSum % P
for cnt, start_prob in centers:
if invM == 1:
sum_q = (cnt % P) * start_prob % P
else:
num = (1 - power(invM, cnt, P) + P) % P
den = (1 - invM + P) % P
sum_q = start_prob * num % P * modInverse(den, P) % P
sumSq = sum_q * sum_q % P
trueSum = 0
p_curr = start_prob
for x in range(cnt):
trueSum = (trueSum + (2*x + 1) * p_curr) % P
p_curr = (p_curr * invM) % P
ans = (ans - sumSq + P) % P
ans = (ans + trueSum) % P
print(ans)
t = int(input())
for _ in range(t):
solve()