Magical Cow Stacks

The cows from the farm have joined the traveling circus and are about to perform a dramatic act on a circular stage consisting of \(N\) platforms. On each platform, a stack of cows is formed with a height between 1 and \(N\) (inclusive). When the ringmaster gives the signal, every stack falls to its clockwise neighbor in a special way: the bottom cow stays on its platform, the cow immediately above falls one platform clockwise, the next cow falls two platforms clockwise, and so on. When the cows land on a platform, they form a new stack (which does not fall further).

A configuration of stack sizes \(a_0, a_1, \dots, a_{N-1}\) is called magical if, after all stacks fall, the new stack on each platform has the same number of cows as the original stack on that platform. Formally, if each platform \(i\) (with \(0 \le i (i-j) \bmod N\bigr), \] where \(\mathbf{1}(\cdot)\) is the indicator function. Your task is to compute the number of magical configurations modulo \(10^9+7\).

Observation: It turns out that the only magical configurations are the ones where every platform has the same number of cows. Since each \(a_i\) can be any integer from 1 to \(N\), there are exactly \(N\) magical configurations.

Input/Output Example: For example, if \(N=3\), the only magical configurations are \((1,1,1)\), \((2,2,2)\), and \((3,3,3)\), so the answer is 3.

inputFormat

The input consists of a single integer \(N\) (\(1 \leq N \leq 10^9\) or as specified by the problem constraints), which denotes the number of platforms arranged in a circle.

outputFormat

Output a single integer — the number of magical configurations modulo \(10^9+7\).

sample

1

1