Count of Array solution codechef

 

You love array, don’t you?

You are given two integer NN and MM, along with an array BB of length NN containing pairwise distinct integers. You have to find the number of array AA of length NN satisfying the follow conditions:

1. 1≤Ai≤M1≤Ai≤M.
2. Ai≠AjAi≠Aj for all 1≤i<j≤N1≤i<j≤N.
3. Ai≠BiAi≠Bi for all 1≤i≤N1≤i≤N.

Since the answer can be very large, output it under modulo 109+7109+7.

Input Format

• The first line of the input contains two space-separated integers NN and MM.
• The second line of the input contains NN separated integers B1,B2,…,BNB1,B2,…,BN – the array BB.

Output Format

Output on a single line the number of satisfactory array modulo 109+7109+7.

Constraints

• 1≤N≤2⋅1051≤N≤2⋅105
• 1≤M≤3⋅1051≤M≤3⋅105
• 1≤Bi≤1091≤Bi≤109
• Bi≠BjBi≠Bj for all 1≤i<j≤N1≤i<j≤N.

Sample Input 1 

3 4
5 1 2

Sample Output 1 

14

Explanation

All satisfactory arrays are:

• [1,2,3][1,2,3]
• [2,3,1][2,3,1]
• [3,2,1][3,2,1]
• [1,2,4][1,2,4]
• [2,4,1][2,4,1]
• [4,2,1][4,2,1]
• [1,3,4][1,3,4]
• [1,4,3][1,4,3]
• [3,4,1][3,4,1]
• [4,3,1][4,3,1]
• [2,3,4][2,3,4]
• [2,4,3][2,4,3]
• [3,2,4][3,2,4]
• [4,2,3][4,2,3]

Sample Input 2 

2 2
1 3

Sample Output 2 

1

Explanation

The only satisfactory array is:

• [2,1]
  

  For Solution

  Click Here!