ThePermutationGame | Topcoder Archive

Problem Statement

Alice and Bob are playing a game called "The Permutation Game". The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first N positive integers. Let p be Bob's permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice's final value will be f(x). Alice wants to choose the smallest x such that f(x) = 1 for any permutation Bob can provide. Compute and return the value of such x modulo 1,000,000,007.

Definition

Class:: ThePermutationGame
Method:: findMin
Parameters:: int
Returns:: int
Method signature:: int findMin(int N)
(be sure your method is public)

Notes

A permutation of the first N positive integers is a sequence of length N that contains each of the integers 1 through N exactly once. The i-th (1-indexed) element of a permutation p is denoted by p[i].

Constraints

N will be between 1 and 100,000 inclusive.

Examples

```
2
```
```
Returns: 2
```
Bob can choose the permutations (1,2) or (2,1). If Alice chooses 1, then, Bob can choose the permutation (2,1), which would would make f(1) = 2. However, if Alice chooses 2, no matter which permutation Bob chooses, Alice will get f(2) = 1. Thus the answer in this case is 2.
```
3
```
```
Returns: 6
```
```
11
```
```
Returns: 27720
```
```
102
```
```
Returns: 53580071
```
```
9999
```
```
Returns: 927702802
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.