A teacher is going to deliver N gifts to N students in the class. Every student can get exactly one gift. Since the value of each gift is different, the teacher decides to deliver the gifts based on student ranks. Thus, he evaluates each gift with a value T, which means only the students who rank higher than or equal to T are allowed to receive that gift. You are asked to write a program counting how many ways there are for the teacher to deliver those gifts.
For example, there are 3 students in the class (N=3), and the 3 gifts are valued as 2, 3, 3. So there are 4 different ways to deliver those gifts: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, where a solution {a, b, c} means the first gift (with value 2) is delivered to the student with rank a, the second gift (with value 3) is delivered to the student with rank b, and the last gift (with value 3) is delivered to the student with rank c.
The first line contains a positive integer N.
The second line consists of N positive integers, indicating the values Ti of the N gifts.
1 ≤ N ≤ 20
1 ≤ Ti ≤ N
T1 ≤ T2 ≤ ... ≤ TN-1 ≤ TN
(That is, the values of the gifts have been sorted for you.)
Please output an integer, indicating how many ways there are to deliver those gifts.