题目思路

思维题，全排列从1开始考虑，假设现在数组中有cnt[1]个1，那么我们只能留下一个作为1，剩下的都需要加1，这样有cnt[1]种选择。

然后再看2，同样地，cnt[2]需要加上cnt[1]-1的数量，我们也只能保留一个，剩下的全部加一，此时有cnt[1] * (cnt[2] + cnt[1] - 1)种情况。

这样不断地累乘下去就是最终的答案了，注意会爆int。

代码

题目描述

塔子哥有一个数组，他能操作若干次，每次可以选择一个元素+1。

塔子哥想知道，最多能生成多少种不同的排列？

定义：排列指长度为$n$的数组，1到n每个元素都只出现一次。

输入描述

第一行一个正整数$n(\le 10^5)$，代表数组大小。

第二行$n$个正整数$a_i(\le 10^5)$

输出描述

一个整数，代表方案数，对10^9+7取模

样例

输入

3
1 2 1

输出

4