Чемпионат по Кальвинболу
В дополнение к чемпионату CEOI и хоккею с шайбой, в этом году в Чехии также проводится чемпионат по кальвинболу. Мы не будем вдаваться в квази-существующие правила кальвинбола, а вместо этого сосредоточимся на процедуре выбора команды.
В кальвинбол играют n игроков с разными именами, разделенными на любое количество непустых команд. Для записи команд используется следующее соглашение. Во-первых, в каждой команде игрок с лексикографически наименьшим именем выступает капитаном команды. Затем команды сортируются лексикографически по именам их капитанов и нумеруются последовательными целыми числами, начиная с 1. Наконец, игроки перечисляются в лексикографическом порядке вместе с номерами их команд.
Например, если существуют три команды - одна состоит из Calvin, Hobbes и Susie, одна из Tom и Jerry, одна только из Batman, то список игроков будет выглядеть следующим образом:
Batman 1
Calvin 2
Hobbes 2
Jerry 3
Susie 2
Tom 3
Каждый день чемпионата играют одни и те же игроки, но каждый раз выбираются разные команды. Так как каждый день выступают одни и те же игроки, для краткости опустим их имена в списке. Список игроков будем представлять последовательностью номеров команд (1 2 2 3 2 3 в приведенном выше примере). Чемпионат заканчивается, когда все возможные варианты команд будут опробованы.
Поскольку существует много возможных разбиений на командны, решение на каждый день было довольно запутанным. В этом году Международная организация Дезорганизация Кальвинбола решила, что выбор команд будет сделан в соответствии с лексикографическим порядком последовательностей, которые их представляют. Итак, в первый день все игроки будут в одной команде (последовательность 1 1 1 1 1 1), во второй день все играют против Тома (последовательность 1 1 1 1 1 2), ..., и в последний день все играют против всех (последовательность 1 2 3 4 5 6).
Для заданной записи команд определите, в какой день турнира она будет использована. Ответ выведите по модулю1000007.
Обратите внимание, что имена игроков в примере приведены только для пояснения, и они не играют никакой роли в реальном задании.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10000). Вторая строка содержит n натуральных чисел, задающих описание команд как указано в условии задачи.
Выходные данные
Выведите номер дня чемпионата, в котором будет использоваться заданное распределение команд по модулю 1000007. Первый день чемпионата имеет номер 1.