import sys
input = sys.stdin.readline

from collections import Counter

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

C=Counter()

L=[0]*B
for i in range(B):
    p=pow(i,N,B)
    L[i]=p

    C[p]+=1

ANS=0
for i in range(B):
    for j in range(B):
        to=(L[i]+L[j])%B
        ANS+=C[to]

print(ANS)