Essentially Different Colorings on a Cycle

You are given a cycle consisting of \(n\) vertices and \(n\) edges, along with \(n\) distinct colors. Each vertex is to be colored with one of the \(n\) colors. Two colorings are considered the same if one can be obtained from the other by a rotation. Compute the number of essentially different colorings modulo \(10^9+7\). The answer is defined under rotational symmetry, i.e., colorings that can be rotated to coincide are considered identical.

Note: The problem requires you to count colorings up to rotation equivalence.

Hint: You might find Burnside's lemma (or the Polya enumeration theorem) useful. In particular, the number of different colorings is given by:

[ \frac{1}{n} \sum_{r=0}^{n-1} n^{\gcd(n,r)} \mod (10^9+7)]

inputFormat

The input consists of a single integer \(n\) (\(1 \le n\le 10^5\)), representing the number of vertices of the cycle and the number of available colors.

outputFormat

Output a single integer, the number of essentially different colorings of the cycle modulo \(10^9+7\).

sample

1

1