JOIN

 Problem Statement

Problem Statement for ThePermutationGame

### 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

0)

 `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.
1)

 `3`
`Returns: 6`
2)

 `11`
`Returns: 27720`
3)

 `102`
`Returns: 53580071`
4)

 `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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 652 Round 1 - Division I, Level One