As behooves any intelligent schoolboy, Kevin Sun is studying psycowlogy, cowculus, and cryptcowgraphy at the Bovinia State University (BGU) under Farmer Ivan. During his Mathematics of Olympiads (MoO) class, Kevin was confronted with a weird functional equation and needs your help. For two fixed integers k and p, where p is an odd prime number, the functional equation states that $f(k x \operatorname{mod} p) \equiv k \cdot f(x) \operatorname{mod} p$ 

for some function $f : \{0,1,2, \cdots, p - 1 \} \rightarrow \{0,1,2, \cdots, p - 1 \}$. (This equation should hold for any integer x in the range 0 to p - 1, inclusive.)

It turns out that f can actually be many different functions. Instead of finding a solution, Kevin wants you to count the number of distinct functions f that satisfy this equation. Since the answer may be very large, you should print your result modulo 10^9 + 7.


-----Input-----

The input consists of two space-separated integers p and k (3 ≤ p ≤ 1 000 000, 0 ≤ k ≤ p - 1) on a single line. It is guaranteed that p is an odd prime number.


-----Output-----

Print a single integer, the number of distinct functions f modulo 10^9 + 7.


-----Examples-----
Input
3 2

Output
3

Input
5 4

Output
25



-----Note-----

In the first sample, p = 3 and k = 2. The following functions work:   f(0) = 0, f(1) = 1, f(2) = 2.  f(0) = 0, f(1) = 2, f(2) = 1.  f(0) = f(1) = f(2) = 0.

Difficulty: MEDIUM_HARD
Tags: Graph traversal

Combinatorics

Number theory

Mathematics

Spanning trees

Starter code:

Solutions:
MOD = int(1000000000.0 + 7)
(n, k) = map(int, input().split())
if k < 2:
	p = n - (1 - k)
else:
	t = 1
	a = k
	while a != 1:
		a = a * k % n
		t += 1
	p = (n - 1) // t
print(pow(n, p, MOD))


def is_good(f, p, k):
	for i in range(p):
		if f[k * i % p] != k * f[i] % p:
			return False
	return True

def gen(f, p, k, i):
	if i == p:
		return is_good(f, p, k)
	else:
		ans = 0
		for j in range(p):
			f.append(j)
			ans += gen(f, p, k, i + 1)
			f.pop()
		return ans

def solve(p, k):
	num = 0
	used = set()
	for j in range(p):
		if j not in used:
			num += 1
		i = j
		while i not in used:
			used.add(i)
			i = i * k % p
	return pow(p, num - (k != 1), 10 ** 9 + 7)
(p, k) = map(int, input().split())
print(solve(p, k))


q = 10 ** 9 + 7

def solve(p, k):
	if k == 0:
		return pow(p, p - 1, q)
	if k == 1:
		return pow(p, p, q)
	(x, y) = (k, 1)
	while x != 1:
		x *= k
		x %= p
		y += 1
	return pow(p, (p - 1) // y, q)
(p, k) = list(map(int, input().split()))
print(solve(p, k))


def m_pow(x, y, m):
	if y == 0:
		return 1
	if y & 1:
		return m_pow(x, y - 1, m) * x % m
	else:
		t = m_pow(x, y >> 1, m)
		return t * t % m
(p, k) = map(int, input().split())
used = [0] * p
if k == 0:
	print(m_pow(p, p - 1, 1000000007))
else:
	c = 1 if k == 1 else 0
	for x in range(1, p):
		if not used[x]:
			y = x
			while not used[y]:
				used[y] = True
				y = k * y % p
			c += 1
	print(m_pow(p, c, 1000000007))


mod = 10 ** 9 + 7
(p, k) = [int(x) for x in input().split()]
if k == 0:
	print(pow(p, p - 1, mod))
elif k == 1:
	print(pow(p, p, mod))
else:
	z = [1]
	while z[-1] * k % p != z[0]:
		z.append(z[-1] * k % p)
	print(pow(p, (p - 1) // len(z), mod))


MOD = 10 ** 9 + 7

def f(a, b):
	if b == 1:
		return a % MOD
	elif b % 2 == 0:
		return f(a * a % MOD, b // 2)
	else:
		return a * f(a * a % MOD, b // 2) % MOD
(p, k) = map(int, input().split())
if k == 0:
	print(f(p, p - 1))
	exit()
if k == 1:
	print(f(p, p))
	exit()
t = 1
a = k
while a != 1:
	a = a * k % p
	t += 1
n = (p - 1) // t
print(f(p, n))


M = 10 ** 9 + 7

def period(p, k):
	c = 1
	ek = k
	while ek != 1:
		ek = ek * k % p
		c += 1
	return c

def functions(p, k):
	if k == 0:
		return pow(p, p - 1, M)
	elif k == 1:
		return pow(p, p, M)
	else:
		c = (p - 1) // period(p, k)
		return pow(p, c, M)
(p, k) = map(int, input().split())
print(functions(p, k))


__author__ = 'MoonBall'
import sys
T = 1
M = 1000000007

def process():
	(P, K) = list(map(int, input().split()))
	k = [K * x % P for x in range(P)]
	if not K:
		print(pow(P, P - 1, M))
		return
	f = [0] * P
	c = [0] * P
	ans = 1
	for i in range(0, P):
		if f[i]:
			continue
		cnt = 1
		u = i
		f[u] = 1
		while not f[k[u]]:
			u = k[u]
			f[u] = 1
			cnt = cnt + 1
		c[cnt] = c[cnt] + 1
	for i in range(1, P):
		if c[i] != 0:
			cnt = i * c[i] + (1 if i > 1 else 0)
			ans = ans * pow(cnt, c[i], M) % M
	print(ans)
for _ in range(T):
	process()


def main():
	(p, k) = map(int, input().split())
	s = 1
	m = pow(10, 9) + 7
	if k == 0:
		s = pow(p, p - 1, m)
	elif k == 1:
		s = pow(p, p, m)
	else:
		o = 1
		n = k
		while n != 1:
			n = k * n % p
			o += 1
		c = (p - 1) // o
		s = pow(p, c, m)
	print(s % m)
main()


(n, k) = map(int, input().split())
m = 10 ** 9 + 7
if k == 0:
	print(pow(n, n - 1, m))
elif k == 1:
	print(pow(n, n, m))
else:
	c = 1
	x = k
	while x != 1:
		x = x * k % n
		c += 1
	print(pow(n, (n - 1) // c, m))


(p, k) = map(int, input().split())
c = 1000000007
if k == 0:
	answer = pow(p, p - 1, c)
elif k == 1:
	answer = pow(p, p, c)
else:
	size = 1
	nk = k
	while nk != 1:
		size += 1
		nk = nk * k % p
	cycles = (p - 1) // size
	answer = pow(p, cycles, c)
print(answer)


import unittest
import sys

class Binominals:

	def mod(self, a):
		return a % self.m

	def add(self, a, b):
		return (a + b) % self.m

	def mul(self, a, b):
		return a * b % self.m

	def pow(self, e, n):
		r = 1
		while n > 0:
			if n & 1:
				r = self.mul(r, e)
			e = self.mul(e, e)
			n >>= 1
		return r

	def inv(self, a):
		return self.pow(a, self.m - 2)

	def __init__(self, mod=10 ** 9 + 7, maxn=10 ** 5):
		self.m = mod

class Modular:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		[self.p, self.k] = map(int, uinput().split())
		self.M = 10 ** 9 + 7

	def calculate(self):
		result = 0
		bp = Binominals(mod=self.p)
		mm = 1
		for m in range(1, self.p):
			mm = bp.mul(mm, self.k)
			if mm == 1:
				break
		bb = Binominals(mod=self.M)
		if self.k == 0:
			result = bb.pow(self.p, self.p - 1)
		elif self.k == 1:
			result = bb.pow(self.p, self.p)
		else:
			result = bb.pow(self.p, (self.p - 1) // m)
		return str(result)

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '3 2'
		d = Modular(test)
		self.assertEqual(d.k, 2)
		self.assertEqual(d.p, 3)
		self.assertEqual(Modular(test).calculate(), '3')
		test = '5 4'
		self.assertEqual(Modular(test).calculate(), '25')
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Modular(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Modular().calculate())


(p, k) = map(int, input().split())
res = set()
ex = p - 1
if k != 0:
	if k == 1:
		ex = p
	else:
		c = k
		for i in range(p):
			res.add(c)
			c *= k
			c %= p
		ex = (p - 1) // len(res)
ans = 1
for i in range(ex):
	ans *= p
	ans %= 1000000007
print(ans)


(p, k) = map(int, input().split())

def solve(p, k):
	mod = 10 ** 9 + 7
	if k == 1:
		return pow(p, p, mod)
	if k == 0:
		return pow(p, p - 1, mod)
	ps = [k * x % p for x in range(p)]
	n_groups = 0
	visited = [0] * p
	visited[0] = 1
	for (x, px) in enumerate(ps):
		if visited[x]:
			continue
		n_groups += 1
		y = px
		while visited[y] == 0:
			visited[y] = 1
			y = ps[y]
	return pow(p, n_groups, mod)
print(solve(p, k))


from collections import defaultdict, deque
import sys
import bisect
input = sys.stdin.readline
mod = 1000000007

def bfs(root, k, p):
	queue = deque()
	queue.append(root)
	while queue:
		child = queue.popleft()
		if k * child % p not in vis:
			vis.add(k * child % p)
			queue.append(k * child % p)
(p, k) = map(int, input().split())
vis = set()
count = 0
for i in range(1, p):
	if i not in vis:
		bfs(i, k, p)
		count += 1
if k == 1:
	count += 1
print(pow(p, count, mod))


from sys import stdin
c = 10 ** 9 + 7
(p, k) = stdin.readline().rstrip().split(' ')
p = int(p)
k = int(k)
if k == 0:
	print(pow(p, p - 1, c))
elif k == 1:
	print(pow(p, p, c))
else:
	n = k
	order = 1
	while n != 1:
		n = n * k % p
		order += 1
	loops = (p - 1) // order
	print(pow(p, loops, c))


def main():
	t = 1
	a = k
	if k == 0:
		return n - 1
	if k == 1:
		return n
	while a != 1:
		a = a * k % n
		t += 1
		p = (n - 1) // t
	return p
(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
p = main()
print(pow(n, p, mod))


import math

def expmod(base, expon, mod):
	ans = 1
	for i in range(1, expon + 1):
		ans = ans * base % mod
	return ans
(p, k) = input().split()
s = 10 ** 9 + 7
k = int(k)
p = int(p)
ord = 1
done = 0
if k == 0:
	z = p - 1
if k == 1:
	z = p
else:
	for i in range(2, p + 1):
		if done == 0:
			if (p - 1) % i == 0:
				if expmod(k, i, p) == 1:
					ord = i
					done = 1
	z = int((p - 1) / ord)
rem = expmod(p, z, s)
print(int(rem))


from sys import stdin
import sys
sys.setrecursionlimit(10 ** 6)
(n, k) = list(map(int, stdin.readline().strip().split()))

def dfs(n):
	visited[n] = True
	while not visited[adj[n]]:
		n = adj[n]
		visited[n] = True
mod = 10 ** 9 + 7
adj = [-1 for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(n):
	adj[i] = i * k % n
pairs = 0
for i in range(1, n):
	if not visited[i]:
		dfs(i)
		pairs += 1
if k == 1:
	print(pow(n, n, mod))
else:
	print(pow(n, pairs, mod))


(p, k) = map(int, input().split())
m = 10 ** 9 + 7
if k == 0:
	print(pow(p, p - 1, m))
elif k == 1:
	print(pow(p, p, m))
else:
	used = [0] * p
	res = 0
	for i in range(1, p):
		a = i
		if used[a] == 0:
			res += 1
		while used[a] == 0:
			used[a] = 1
			a = k * a % p
	print(pow(p, res, m))


(p, k) = map(int, input().split())
M = 1000000007
if k == 0:
	(print(pow(p, p - 1, M)), exit(0))
if k == 1:
	(print(pow(p, p, M)), exit(0))
(cnt, x) = (0, 1)
while 1:
	cnt -= -1
	x = k * x % p
	if x == 1:
		break
print(pow(p, (p - 1) // cnt, M))


def divisors(n):
	ans = set()
	i = 1
	while i * i <= n:
		if n % i == 0:
			ans.add(i)
			ans.add(n // i)
		i += 1
	return sorted(list(ans))
mod = 10 ** 9 + 7
(p, k) = [int(x) for x in input().split()]
if k == 0:
	print(pow(p, p - 1, mod))
elif k == 1:
	print(pow(p, p, mod))
else:
	for z in divisors(p - 1):
		if (p - 1) % z == 0 and pow(k, z, p) == 1:
			print(pow(p, (p - 1) // z, mod))
			break


import math
(p, k) = map(int, input().split())
a = [0] * p
sets = 0
for i in range(p):
	if a[i] == 0:
		sets += 1
		r = i
		while a[r] == 0:
			a[r] = 1
			r = int(math.fmod(r * k, p))
if k == 0:
	sets = p
elif k == 1:
	sets = p + 1
res = 1
big = 1000000007
for i in range(sets - 1):
	res = int(math.fmod(res * p, big))
print(int(res))