N, B = map(int, input().split())

cnt = [0] * B
for x in range(B):
    cnt[pow(x,N,B)] += 1

ans = 0
for x in range(B):
    for y in range(B):
        c = (pow(x,N,B) + pow(y,N,B)) % B
        ans += cnt[c]

print(ans)