**Introduction**

This section will discuss the problem “Nice Permutations”. First, let’s see the problem statement.

__Problem statement-__

Peter decided to host a party in which ‘**N**’ people gathered to eat. It is given that **i ^{th} **person will eat

**a**plates of food at the party. The plates of food were served in such a way that only one person could go to the food counter at a time and take one plate. So, Peter decides the order which will be followed by the gathered ‘N’ people in going to the food counter and taking the plate of food to eat. Let that order be a permutation ‘

_{i}**P’**of numbers from 1 to N.

( A permutation **P **is an array of integers of size **N, **in which each integer from 1 to N appears exactly once)

The order of people taking the plates of food will go as follows:

- If person ‘P[0]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
- If person ‘P[1]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
- . . . . . . .
- If person ‘P[N-2]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise he will be skipped
- If person ‘P[N-1]’ has some plates left to eat, he will go to the food counter and take one plate, otherwise, he will be skipped
- If there are still people with number of plates left to eat, the process repeats from the start, otherwise, the process ends

According to Peter, a permutation ‘**P**’ is nice if none of the persons get two or more consecutive chances to go to the food counter and take the plates of food.

You will be given **‘N’**, the number of people gathered in Peter’s party and an array **‘arr’** containing N integers, where arr[i] denotes the number of plates that the i^{th} person will eat in the party and your task is to count the number of nice permutations. The answer may be large, so print it modulo 998244353.

Also read, __permutation of string__

Let’s take an example to understand the given problem:

Suppose N = 2 and arr = {1, 2}

It means there are two people who came to Peter’s party and the 1st^{ } person will eat one plate of food and the 2nd person will eat two plates of food.

Permutations of numbers from 1 to 2 are: {1, 2} and {2, 1}

Let's check these two permutations one by one if they are nice or not.

Permutation 1: P1 = {1, 2}

- P1[0] = 1: 1st person will go to the food counter and take one plate. Remaining plate for 1st person = arr[0] - 1 = 1 - 1 = 0

So, arr = {0, 2}

- P1[1] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 2 -1 = 1

So, arr = {0, 1}

One round of the permutation finished but still one plate of food is left for the 2nd person as now arr = {0, 1}. So, the process will repeat from the start.

- P1[0] = 1: 1st person has 0 plates left to eat, so he will be skipped.
- P1[1] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 1 -1 = 0

So, arr = {0, 0}

Now, none of the persons has left any number of plates to eat (as arr has become {0, 0}), so the process will stop. Three plates of food are taken from the food counter and the people reached the food counter in the following order:

{1, 2, 2}

Here we can see that the 2nd person has got two consecutive chances to go to the food counter and take a plate. So, this permutation is not a nice permutation.

Permutation 2: P2 = {2, 1}

- P2[0] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 2 - 1 = 1

So, arr = {1, 1}

- P1[1] = 1: 1st person will go to the food counter and take one plate. Remaining plate for 1st person = arr[0] - 1 = 1 -1 = 0

So, arr = {0, 1}

One round of the permutation finished but still one plate of food is left for the 2nd person as now arr = {0, 1}. So, the process will repeat from the start.

- P2[0] = 2: 2nd person will go to the food counter and take one plate. Remaining plate for 2nd person = arr[1] - 1 = 1 -1 = 0

So, arr = {0, 0}

- P2[1] = 1: 1st person has 0 plates left to eat, so he will be skipped.

Now, none of the persons has left any number of plates to eat (as arr has become {0, 0}), so the process will stop. Three plates of food are taken from the food counter and the people reached the food counter in the following order:

{2, 1, 2}

Here we can see none of the people has got two consecutive chances to go to the food counter and take a plate. So, this permutation is a nice permutation.

So, the total number of nice permutations for N = 2 and arr = {1, 2} is 1.

Now that we understand the problem let's discuss the approach to solve it in the next section.

Also see, __Euclid GCD Algorithm__

##
**Solution Approach**

This section will discuss the approach to solve the problem described in the previous section. We have to find the total number of nice permutations. Here nice permutations means the arrangement of ‘N’ people such that none of them get two consecutive chances to go to the food counter. The exact way in which they are getting the chance to go to the food counter is explained in the previous section.

Suppose the maximum number of plates a person can eat is ‘x’.

Case 1: If there are more than one person who can eat ‘x’ plates of food.

In this case, any permutation of integers from 1 to N will be a nice permutation because in the last round (the x^{th}_{ }round), each of these persons will go one by one and take the plate and none of them will get two consecutive chances to go to the food counter.

Case 2: If there is only one person who can eat ‘x’ plates of food.

Let ‘y’ be the index of the person who can eat the maximum number of plates. Then during the x-th round, there will be only one person left to go to the food counter. So, for a permutation to be a nice permutation, there should be a person in (x-1)-th round to go to the food counter after the y-th person. Let the number of persons who can eat (x-1) plates is ‘k’. If any of these ‘k’ persons will eat after the y-th person in the (x-1)-th round, then the permutation will be nice. We can count the bad permutations where none of the ‘k’ persons will eat after the y-th person in x-th round.

Total number of persons = N

Number of persons who can eat ‘x’ plates of food = 1

Number of persons who can eat ‘x-1’ plates of food = k

Number of persons who won’t eat ‘x’ or ‘x-1’ plates of food = N - k -1

Number of ways of getting bad permutations = (N! / (k+1)!) * (k!) = N! / (k+1)

So, number of good permutations = (Total permutations) - (Number of bad permutations)

= N! - N!/(k+1)

**Algorithm **-

**Step 1**. First, the main function. Inside the main function, create two variables ‘n’ and ‘arr’ to store the number of people at Peter’s party and the number of plates of food that each of these people will eat.

**Step 2**. Next, create the function “nicePermutations()” to find the number of nice permutations. It takes the following input parameters:

- n: Number of people in the party
- arr: Array denoting the number of plates of food that each of these people will eat

**Step 3. ** Inside the function “nicePermutations()”, first initialise a variable ‘maxElement’ equal to the first element of ‘arr’ and then traverse the remaining elements of ‘arr’ and keep updating ‘maxElement’ to store the maximum element of ‘arr’ in it. Then create variables ‘countMaxElement’ and ‘k’ to store the count of ‘maxElement’ and ‘maxElement - 1’ respectively. Traverse the array ‘arr’ to find the value of these two variables.

**Step 4. **Now initialize the variables ‘ans’ and ‘bad’ to store the total number of permutations and number of bad permutations respectively. Run a ‘for loop’ and calculate the value of ‘ans’ and ‘bad’.

**Step 5. **Finally, check if the count of occurrence of ‘maxElement’ is greater than 1, then return the total number of permutations, else subtract the number of bad permutations from the total number of permutations and then return it.