Count of Array CodeChef Solution – Code Drive Solution 2022

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. 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]

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