TopCoder Statistics - Problem Statement

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
35157

Returns: 937518076
34230

Returns: 740350604
57100

Returns: 247067771
58698

Returns: 49268119
12481

Returns: 849911685
42324

Returns: 762823246
31379

Returns: 589672269
24398

Returns: 882274344
36940

Returns: 330451934
24917

Returns: 250138819
31086

Returns: 234840781
26329

Returns: 145436481
10079

Returns: 360516388
72615

Returns: 468013463
13944

Returns: 851198691
8376

Returns: 459278786
40268

Returns: 207985004
53876

Returns: 294846859
57385

Returns: 340995703
87446

Returns: 576510380
20331

Returns: 929584200
76668

Returns: 982058946
18397

Returns: 286495927
75155

Returns: 410672060
33360

Returns: 302893413
57529

Returns: 998094308
62815

Returns: 365884096
88264

Returns: 668415225
87537

Returns: 569631445
25169

Returns: 377880881
133

Returns: 765427742
1381

Returns: 714617036
650

Returns: 179094468
301

Returns: 199546229
170

Returns: 871276406
5

Returns: 60
19640

Returns: 705613344
128

Returns: 570728460
6

Returns: 60
9508

Returns: 220585550
16

Returns: 720720
73

Returns: 497270415
42

Returns: 206169884
753

Returns: 691620754
8

Returns: 840
361

Returns: 779915945
242

Returns: 769677147
941

Returns: 665163605
16

Returns: 720720
1541

Returns: 630801461
448

Returns: 215695038
13

Returns: 360360
70

Returns: 419737080
1311

Returns: 938024783
7

Returns: 420
3

Returns: 6
3105

Returns: 588601036
89893

Returns: 594213079
19414

Returns: 63013446
32570

Returns: 965309544
14371

Returns: 63854004
12386

Returns: 608039160
75747

Returns: 248650835
3743

Returns: 67640556
30487

Returns: 823181278
19852

Returns: 397205410
3699

Returns: 654343651
70458

Returns: 168508059
16422

Returns: 786864642
49978

Returns: 739881009
30027

Returns: 662326482
577

Returns: 970663088
18061

Returns: 492843004
12240

Returns: 159347435
16738

Returns: 903923151
2040

Returns: 675966917
41511

Returns: 149417417
93731

Returns: 489330151
26656

Returns: 544162488
45741

Returns: 495256522
70174

Returns: 223695140
1337

Returns: 232134838
100000

Returns: 59814054
99990

Returns: 26863016
99991

Returns: 59814054
1

Returns: 1
32

Returns: 551882779
99999

Returns: 59814054
12345

Returns: 733823350
70523

Returns: 999268607
65536

Returns: 551585434
4

Returns: 12
98798

Returns: 786222871
96720

Returns: 477016810
9

Returns: 2520
97966

Returns: 744400308

Statistics

Problem Statement for "ThePermutationGame"

Problem Statement

Definition

Notes

Constraints

Examples