Taro's Rabbit Numbering

Taro has \(N\) rabbits. In order to identify them easily, he plans to assign each rabbit a unique number. However, each rabbit \(i\) prefers a number between \(1\) and \(M_i\) (inclusive). The task is to count the number of ways to assign each rabbit a distinct number satisfying its preference.

Formally, you are given an integer \(N\) and \(N\) integers \(M_1, M_2, \dots, M_N\). You need to assign a distinct number \(a_i\) to each rabbit \(i\) such that \(1 \le a_i \le M_i\). Output the total number of ways to do this, taken modulo \(10^9+7\). If no valid assignment exists, output \(0\).

Hint: A good approach is to sort the \(M_i\) values and count the valid choices for each rabbit incrementally.

inputFormat

The first line contains a single integer \(N\) (the number of rabbits).

The second line contains \(N\) space-separated integers \(M_1, M_2, \dots, M_N\), where each \(M_i\) represents the maximum number that rabbit \(i\) accepts.

outputFormat

Output a single integer representing the number of distinct valid assignments modulo \(10^9+7\). If no valid assignment exists, output \(0\).

sample

1
5

5