N, P = map(int, input().split())
A = int(N ** (N**N))
mod = 10**9 + 7
B = 0
while A != 0:
    if A % P == 0:
        A = int(A // P)
        B += 1
    else:
        break
print(B % mod)