Moodular Arithmetic
Contest: Codeforces Round 334 (Div. 1)
Difficulty rating: 1800
Tags: combinatorics, dfs and similar, dsu, math, number theory

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(kx \mod p) \equiv k \cdot f(x) \mod p$$

for some function $$f: \{0, 1, 2, \cdots, p-1\} \to \{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 109 + 7.

Input format:
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 format:
Print a single integer, the number of distinct functions f modulo 109 + 7.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, p = 3 and k = 2. The following functions work:

1. f(0) = 0, f(1) = 1, f(2) = 2.
2. f(0) = 0, f(1) = 2, f(2) = 1.
3. f(0) = f(1) = f(2) = 0.

Example input:
3 2

Example output:
3

Example input:
5 4

Example output:
25

Editorial:
Hint: First there are special cases k = 0 and k = 1. After clearing these out, think about the following: given the value of f(n) for some n, how many other values of f can we find?
We first have the degenerate cases where k = 0 and k = 1. If k = 0, then the functional equaton is equivalent to f(0) = 0. Therefore, pp - 1 functions satisfy this, because the values f(1), f(2), ..., f(p - 1) can be anything in {0, 1, 2, ..., p - 1}.
If k = 1, then the equation is just f(x) = f(x). Therefore pp functions satisfy this, because the values f(0), f(1), f(2), ..., f(p - 1) can be anything in {0, 1, 2, ..., p - 1}.
Now assume that k ≥ 2, and let m be the least positive integer such that $$k^m \equiv 1 \mod p$$ This is called the order of $$k \mod p$$ First, plug in x = 0 to find that $$f(0) = k \cdot f(0) \implies (k - 1)f(0) = 0 \implies f(0) = 0 \mod p$$ as p is prime, and $$k \neq 1$$. Now for some integer $$n \neq 0$$, choose a value for f(n). Given this value, we can easily show that $$f(k^{i}n \mod p) \equiv k^{i}f(n) \mod p$$ just by plugging in x = ki - 1n into the functional equation and using induction. Note that the numbers n, kn, k2n, ..., km - 1n are distinct $$\bmod p$$, since m is the smallest number such that $$k^m \equiv 1 \mod p$$. Therefore, if we choose the value of f(n), we get the value of m numbers ($$f(n), f(kn \mod p), \ldots, f(k^{m-1}n \mod p)$$). Therefore, if we choose f(n) of $${ \frac { p - 1 } { m } }$$ integers n, we can get the value of all p - 1 nonzero integers. Since f(n) can be chosen in p ways for each of the $${ \frac { p - 1 } { m } }$$ integers, the answer is $$p^{\frac{p-1}{m}}$$.
Another way to think about this idea is to view each integer from 0 to p - 1 as a vertex in a graph, where n is connected to $${ k ^ { i } n \mod p }$$ for every integer i. If we fix the value of f(n) for some n, then f also becomes fixed for all other vertices in its connected component. Thus our answer is p raised to the the number of connected components in the graph.
Challenge: How quickly can we find m? For this problem we let O(p) pass, but faster methods certainly exist. (This is a very open-ended question.)