Once Sasha decided that a random shuffler in his favourite media player
should be replaced. Sasha wants to calculate the order of songs according
to the following rule:
x0 = 0,
xi = (xi − 1 · a + b) mod m,
is the total number of songs, a
are integers in range from 0 to m
Generated sequence of song numbers should satisfy the following rules:
- x0 … xm − 1 should be a permutation of integers from 0 to m − 1,
- xm should be equal to zero.
Sasha wants to find all pairs (ai
), resulting in a valid sequences and calculate the average among all ai
. Help him do it.
The input consists of at most 100 test cases. Each test case is a single line containing an integer m (1 < m < 109).
For each test case output in a single line the average among ai, rounded down.
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010.