About Count of Array CodeChef Solution
- This is a coding contest based on algorithms, data structures, and problem-solving.
- Organizer: The contest is hosted by NIT Trichy.
- Prizes: NA
- Registrations for prizes: NA
Problem: Count of Array CodeChef Solution
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≤Ai≤M1≤Ai≤M.
- Ai≠AjAi≠Aj for all 1≤i<j≤N1≤i<j≤N.
- 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]
Contest Details:
- This is an External Rated Contest.
- Duration: 3 Hours
- Start time: 30th December 2021, 20:00 hrs IST
- End time: 30th December 2021, 23:00 hrs IST
You may check your timezone here. - This contest is rated only for Division 2 and Division 3 users. Division 1 users can participate unofficially in this contest.
Get More CodeChef Solution >>
Substring Minimum Function FizzBuzz Solution
Magical Planks Fizzbuzz Solution
Favourite String of Chef CodeChef Solution
Sum this up Code Chef Solution
Game between friends CodeChef Solution
