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

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

ans = 0
xx = [pow(x,N,B) for x in range(B)]

for i in range(B):
    for j in range(B):
        c = (xx[i] + xx[j]) % B
        ans += cntz[c]

print(ans)