bananadance

As you may know, cows have recently acquired a taste for bananas. When two cows who are friends eat bananas together, there is a chance that they will get banana fever. However, this issue has been solved so well by our friendly programmers that cows have been eating more bananas than before, resulting in a shortage of bananas now. This has caused the price of bananas to skyrocket due to an inelastic supply curve usually associated with agriculture products. To remedy this, either the supply of bananas need to be increased or the demand for bananas should be reduced. However, as cows love bananas, the latter is not an option.

In order to increase the supply of bananas, one must increase the yield of banana plantations. (You don't say.) In order to wish for a larger yield of bananas in the next harvesting season, Haymouth the cow and his friend Moosa decided to co-ordinate an impressive banana dance as an offering to Hubert, the god (of bananas). It is rumoured that Hubert will be able to make bananas grow faster, just like how the Bell Curve God will magically make your grades appear higher.

The amount of bananas that will be harvested in the next harvest season is believed to depend on the impressiveness of the banana dance. Hubert the god loves long banana dances. Hence, the impressiveness of the banana dance is directly proportional to the duration of the banana dance. As such, Haymouth and Moosa wants you to find out how many time intervals the banana dance will take, before they decide to go ahead with the dance. All banana dances will take at least 1 time interval and can last very, very, very long. Time intervals are segments of the banana dance where by cows will differ in their relative positions between the segments. As this number can be very huge, you are to output the remainder of this number after dividing by M.

There are many versions of the banana dance and your code will be ran once for each version of the banana dance. The banana dance involves N cows and the number of cows for different versions of banana dance varies. However, the similarity of all the versions of banana dance is that the initial and final configuration of cows remain the same.

The banana dance starts off with the N cows lined up in a straight line. These cows are labelled from 1 to N from left to right and will each move to a new position at the next time interval. When we say cow 1 moves to position 3, it means that cow 1 moves to the initial position of cow 3 at this time interval. It is noted that no two cows will be asked to occupy the same position at the same time interval. This process of labelling and moving will repeat throughout the banana dance. Do note that the movement of cows remain similar for the whole banana dance as well. (Eg. All the cows with label 1 will always move to position 3 in the next time interval)

Input

The first line of input will consist of two integers N, followed by M.

The following N lines will contain one integer each. The i^th integer will denote which position the i^th cow will go after every time interval.

Output

Output a single integer, denoting how many time segments the banana dance takes. As this number can be very huge, you are to output the remainder of this number after dividing by M.

Subtasks

For all testcases, 0 < M ≤ 2000000000 and M is guaranteed to be a prime number.

Subtask 1 (18%): 1 ≤ N ≤ 50. The total duration of the banana dance is not longer than 10¹⁸ time intervals.

Subtask 2 (23%): 1 ≤ N ≤ 5000. The total duration of the banana dance is not longer than 10¹⁸ time intervals.

Subtask 3 (30%): 1 ≤ N ≤ 250000. The total duration of the banana dance is not longer than 10¹⁸ time intervals.

Subtask 4 (2%): 1 ≤ N ≤ 5000000. Also, the i^th cow will always move to the (i mod N) + 1 position.

Subtask 5 (27%): 1 ≤ N ≤ 5000000.

Subtask 6 (0%): Sample Testcases

Sample Input 1

6 5
2
3
4
5
6
1

Sample Output 1

1

After 6 time intervals, the cows will be in the same configuration as their initial configuration. The output is 1 because the remainder of 6 when divided by 5 is 1.

Sample Input 1

6 17
4
6
5
1
2
3

Sample Input 2

4

Original Configuration: ABCDEF

After 1 time interval: DEFACB

After 2 time intervals: ACBDFE

After 3 time intervals: DFEABC

After 4 time intervals: ABCDEF