eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Подсчет деревьев

Подсчет деревьев

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Ваш друг Дарвин - очень известный естествоиспытатель, и рассказывает Вам, что в настоящее время пытается подсчитать количество разновидностей очень определенных видов деревьев, которые он обнаружил два года назад.

Он говорит Вам, что эти деревья очень своеобразны. Во-первых, они плоские: одна сторона обращена на юг, а другая - на север. Во-вторых, когда одна из их ветвей разделяется, она разделяется ровно на две части, которые идут в двух противоположных направлениях: одна идет на запад, а другая - на восток. В общем, такое дерево очень легко представить в виде двоичного дерева, к которому привыкли компьютерные ученые (математически двоичное дерево - это либо пустое дерево, либо внутренний узел с двумя дочерними элементами, которые сами являются двоичными деревьями).

Как великий программист, Вы приходите в восторг, как только слышите о бинарных деревьях. Дарвин продолжает свои объяснения: у такого дерева ветви либо горизонтальны, либо идут вверх. По-прежнему одержимый бинарными деревьями, Вы понимаете, что это соответствует утверждению, что в представлении бинарного дерева, если внутренние узлы помечены высотой (расстоянием от земли) соответствующей ветви, то метка некорневого узла всегда больше или равна метке своего родителя. Пустые деревья не маркируются.

Хотя Вы находите это свойство довольно скучным и не очень интересным, Дарвин продолжает и рассказывает Вам действительно удивительный и тонкий факт, который он недавно обнаружил о своих любимых видах деревьев. После продолжительного обсуждения с Дарвином Вы наконец понимаете, что это свойство может быть просто выражено в виде двоичного дерева. А именно, если выполнить inorder обход помеченного двоичного дерева любого дерева этого вида, результирующая последовательность высот всегда будет одинаковой! (Обход пустого дерева в порядке следования - это пустая последовательность, и, если дерево не пусто, его inorder обход представляет собой конкатенацию inorder обхода левого поддерева, метки верхнего узла, и inorder обхода правого поддерева).

Услышав впечатляющие результаты исследований Вашего друга, Вы призываете его подробно рассказать о методологии, которую он использует для подсчета разновидностей этого особенно удивительного вида. Это заставляет его раскрыть гипотезу, над которой он в настоящее время работает: каждое дерево данного сорта представлено одним и тем же двоичным деревом, которое однозначно идентифицирует это разнообразие. Более того, каждое помеченное двоичное дерево, проверяющее вышеуказанные условия, действительно соответствует существующей разновидности. Дарвин считает, что тогда для подсчета разновидностей можно было бы использовать какой-то математический инструмент, но у него недостаточно математических знаний для этого.

Теперь, когда Вы действительно впечатлены работой Дарвина, Ваша очередь: произвести на него впечатление, написав программу, которая подсчитывает количество разновидностей этого вида.

Вхідні дані

Состоит из следующих строк:

  • в первой строке: количество n элементов последовательностей высот, полученных при обходе любого дерева вида в порядке inorder;

  • n следующих строк представляют собой последовательность высот в миллиметрах с одним целым числом в строке.

И число n, и отметки высот больше или равны 0 и меньше или равны 1 000 000.

Вихідні дані

Выведите одно целое число - количество разновидностей деревьев в виде по модулю 1 000 000 007.

Приклад

Вхідні дані #1
6
3
1
6
2
4
5
Вихідні дані #1
1
Вхідні дані #2
6
1
1
1
1
1
1
Вихідні дані #2
132
Джерело 2019 ACM Southwestern Europe Regional Contest (SWERC), Париж, Январь 26 (2020), Задача J