Підрахунок дерев дерев
Ваш друг Дарвін — відомий натураліст, і він розповідає вам, що зараз намагається підрахувати кількість різновидів певних видів дерев, які він виявив два роки тому.
Він пояснює, що ці дерева дуже особливі. По-перше, вони плоскі: одна сторона звернена на південь, а інша — на північ. По-друге, коли одна з їхніх гілок розгалужується, вона ділиться рівно на дві частини, які спрямовані в протилежні боки: одна йде на захід, а інша — на схід. Загалом, таке дерево легко уявити у вигляді двійкового дерева, до якого звикли комп'ютерні вчені (математично двійкове дерево — це або порожнє дерево, або внутрішній вузол з двома дочірніми елементами, які самі є двійковими деревами).
Як досвідчений програміст, ви захоплюєтеся, почувши про двійкові дерева. Дарвін продовжує: у таких дерев гілки або горизонтальні, або спрямовані вгору. Ви розумієте, що це відповідає твердженню, що в представленні двійкового дерева, якщо внутрішні вузли позначені висотою (відстанню від землі) відповідної гілки, то позначка некореневого вузла завжди більша або дорівнює позначці свого батька. Порожні дерева не маркуються.
Хоча ця властивість здається вам не дуже цікавою, Дарвін розповідає про дивовижний факт, який він нещодавно виявив про ці дерева. Після тривалого обговорення ви розумієте, що ця властивість може бути виражена у вигляді двійкового дерева. А саме, якщо виконати inorder обхід позначеного двійкового дерева будь-якого дерева цього виду, результуюча послідовність висот завжди буде однаковою! (Обхід порожнього дерева в порядку слідування — це порожня послідовність, і, якщо дерево не порожнє, його inorder обхід представляє собою конкатенацію inorder обходу лівого піддерева, позначки верхнього вузла, і inorder обходу правого піддерева).
Вражений дослідженнями Дарвіна, ви просите його детально розповісти про методологію підрахунку різновидів цього виду. Він розкриває гіпотезу, над якою працює: кожне дерево даного сорту представлене одним і тим же двійковим деревом, яке однозначно ідентифікує цю різноманітність. Більше того, кожне позначене двійкове дерево, яке відповідає вищезазначеним умовам, дійсно відповідає існуючій різноманітності. Дарвін вважає, що для підрахунку різновидів можна використати математичний інструмент, але у нього недостатньо математичних знань для цього.
Тепер, коли ви вражені роботою Дарвіна, ваша черга: вразити його, написавши програму, яка підраховує кількість різновидів цього виду.
Вхідні дані
Складаються з наступних рядків:
у першому рядку: кількість n елементів послідовностей висот, отриманих при обході будь-якого дерева виду в порядку inorder;
n наступних рядків представляють собою послідовність висот у міліметрах з одним цілим числом у рядку.
І число n, і позначки висот більше або дорівнюють 0 і менше або дорівнюють 1 000 000.
Вихідні дані
Виведіть одне ціле число — кількість різновидів дерев у виді за модулем 1 000 000 007.