Number Of Permutations

Easy

0/40

0 upvote

Asked in company

Problem statement

There's going to be a contest, in which Ayan is setting questions since they require a lot of time he has asked his friends for help in setting a Hard question. Since the question is really Hard (lol) the statement is going to be on point, Here goes nothing.

"Cow looks for hay, wolf looks for prey. One is killer, other buffet."

Given a list of N integers, find out the number of permutations such that the first and last element are same ?

Since the answer can get very big, print the answer mod 1000000009

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

First Line contains N denoting the number of elements
Second Line contains N space separated integers denoting the numbers A[1...N].`

Output Format :

Output the number of permutations with first and last element of array are same mod 10^9 + 9`

Constraints:

1 <= N <= 100000
1 <= A[i] <= 100000`

Sample Input:

3
1 1 1

Sample Output:

Number Of Permutations

Console