The Ultimate Element

ID: 17387

Type: Default

1000ms

256MiB

In this problem, God has created a series of elements in a very peculiar way. Initially, we define an array as follows:

a_0 = 1, \quad a_n = 2^{a_{n-1}}

For any positive integer p, we are interested in the value of

b_n = a_n \bmod p

It can be proven that for any valid p (chosen so that the following process eventually stabilizes), there exists an index N such that for all n \ge N the value b_n remains constant. In other words, the recurrence

x \to 2^x \bmod p

has a fixed point when iterated starting from 1. Your task is to compute this fixed point value.

Since the number of types of the final element is astronomically huge, you are only required to output the fixed point value modulo p.

inputFormat

The input consists of a single integer p (p > 0) representing the modulus.

It is guaranteed that for the given p the sequence defined by x₀ = 1 and x_n+1 = 2^(x_n) modulo p eventually reaches a fixed point.

outputFormat

Output a single integer — the fixed point value x such that

x = 2^x \bmod p.

#P4139. The Ultimate Element

The Ultimate Element