Clocked State Transition Circuit Period

In a synchronous sequential circuit, there are n states labeled \(S_0, S_1, \ldots, S_{n-1}\). The state transition depends on the clock pulse. When the next clock pulse is high (1), the state \(S_x\) transitions to \(S_{(x\times a + c) \bmod n}\); when the next pulse is low (0), the state \(S_x\) transitions to \(S_{(x\times b + d) \bmod n}\). The clock pulse sequence is fixed and alternates as 1, 0, 1, 0, \(\ldots\).

A complete state is defined by both the node \(S_x\) and the upcoming pulse value. That is, the state is a pair \((x, p)\) with \(p\in\{0,1\}\). The transition function \(f\) is defined as follows:

• If the current state is \((x,1)\) (i.e. the next pulse is 1), then

[ f((x,1)) = \Big( (x\times a + c) \bmod n,\ 0 \Big), ]

• If the current state is \((x,0)\) (i.e. the next pulse is 0), then

[ f((x,0)) = \Big( (x\times b + d) \bmod n,\ 1 \Big). ]

The problem asks: does there exist a clock period \(T\) (which will necessarily be even) such that for every state \((x, p)\), after \(T\) pulses the state returns to itself? If so, report the minimum such period \(T_{\min}\); otherwise, output inf.

Note: For a valid period to exist, the entire state transition function must be a permutation over the set of \(2n\) states. In other words, both mappings \(x\to (x\times a+c)\bmod n\) and \(x\to (x\times b+d)\bmod n\) must be bijections on \(\{0,1,\ldots,n-1\}\). This is equivalent to requiring \(\gcd(a, n) = 1\) and \(\gcd(b, n) = 1\).

inputFormat

The input consists of a single line with five integers: n a b c d, where:

• \(n\) is the number of states.
• \(a, c\) define the transition when the next pulse is high (1): \(S_x \to S_{(x\times a + c) \bmod n}\).
• \(b, d\) define the transition when the next pulse is low (0): \(S_x \to S_{(x\times b + d) \bmod n}\).

The clock signal pulses alternate in the fixed sequence: 1, 0, 1, 0, ...

outputFormat

Output the minimum clock period \(T_{\min}\) (an even number) such that for every state \((S_x, p)\) the system returns to its initial configuration after \(T_{\min}\) pulses. If no such period exists, output inf.

sample

5 1 1 0 0

2