| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 15 | 12 | 7 | 70.000% |
На очередном уроке физкультуры Фома придумал интересное занятие.
После того как школьники выстроились в шеренгу, он дал каждому свой персональный номер. Теперь он просит школьников разбится на группы, чтобы выполнялись условия:
Перебрав несколько способов, Фома заинтересовался, сколько их может быть всего. Он просит вас написать программу, которая вычислит, сколько есть способов разбиения школьников на такие группы.
В первой строке входного файла задано число $n$ (1ドル \le n \le 5000$) --- количество школьников. Во второй строке содержатся $n$ чисел $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 10^9$) --- персональный номер каждого школьника.
В единственной строке выходного файла выведите одно число --- количество способов разделить школьников на группы. Ответ может быть очень большой, поэтому нужно вывести его по модулю 10ドル^9+7$.
4 1 2 3 4
8
5 1 2 2 2 1
15
5 1 2 1 2 1
8