Чемпіонат з Кальвінболу
У доповнення до чемпіонату 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.