eolymp
bolt
Try our new interface for solving problems
Məsələlər

Чемпионат по Кальвинболу

Чемпионат по Кальвинболу

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

В дополнение к чемпионату 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.

Обратите внимание, что имена игроков в примере приведены только для пояснения, и они не играют никакой роли в реальном задании.

Giriş verilənləri

Первая строка содержит одно целое число n (1n10000). Вторая строка содержит n натуральных чисел, задающих описание команд как указано в условии задачи.

Çıxış verilənləri

Выведите номер дня чемпионата, в котором будет использоваться заданное распределение команд по модулю 1000007. Первый день чемпионата имеет номер 1.

Nümunə

Giriş verilənləri #1
3
1 2 2
Çıxış verilənləri #1
4
Mənbə 2015 CEOI День 1, Задача B