Ağacların sayılması

Sizin dostunuz Darvin çox məşhur bir təbiətşünasdır və sizə iki il əvvəl kəşf etdiyi çox spesifik ağac növlərinin sayını hesablamağa çalışdığını söyləyir.

O sizə deyir ki, bu ağaclar çox özünəməxsusdur. Birincisi, onlar düzdür: bir tərəfi cənuba, digəri isə şimala baxır. İkincisi, onların budaqlarından biri bölünəndə, o, tam iki hissəyə bölünür və bu hissələr əks istiqamətlərdə gedir: biri qərbə, digəri isə şərqə gedir. Ümumiyyətlə, belə bir ağacı kompüter alimlərinin alışdığı ikili ağac kimi təsəvvür etmək çox asandır (riyazi olaraq ikili ağac ya boş ağacdır, ya da iki qız elementi olan daxili bir düyündür ki, onlar özləri də ikili ağaclardır).

Böyük bir proqramçı olaraq, ikili ağaclar haqqında eşidəndə həyəcanlanırsınız. Darvin izahatlarına davam edir: belə bir ağacın budaqları ya üfüqi, ya da yuxarıya doğru gedir. Hələ də ikili ağaclarla məşğul olan siz, bunun ikili ağac təsvirində, daxili düyünlərin hündürlüyü (yerdən məsafə) ilə işarələndiyi halda, kök olmayan düyünün işarəsinin həmişə valideyninin işarəsindən böyük və ya bərabər olduğunu başa düşürsünüz. Boş ağaclar işarələnmir.

Baxmayaraq ki, siz bu xüsusiyyəti olduqca darıxdırıcı və çox da maraqlı hesab etmirsiniz, Darvin davam edir və sizə sevimli ağac növləri haqqında son zamanlarda kəşf etdiyi həqiqətən heyrətamiz və incə bir faktı izah edir. Darvinlə uzun müzakirədən sonra nəhayət başa düşürsünüz ki, bu xüsusiyyət sadəcə ikili ağac şəklində ifadə edilə bilər. Yəni, bu növ ağacın hər hansı bir ağacının işarələnmiş ikili ağacının inorder keçidini etsəniz, nəticə hündürlüklərin ardıcıllığı həmişə eyni olacaq! (Boş ağacın inorder keçidi boş ardıcıllıqdır və əgər ağac boş deyilsə, onun inorder keçidi sol alt ağacın inorder keçidinin, yuxarı düyünün işarəsinin və sağ alt ağacın inorder keçidinin birləşməsidir).

Dostunuzun tədqiqat nəticələrindən təsirləndikdən sonra, onu bu xüsusilə heyrətamiz növün müxtəlifliyini hesablamaq üçün istifadə etdiyi metodologiyanı ətraflı izah etməyə çağırırsınız. Bu, onu hazırda üzərində işlədiyi hipotezi açıqlamağa məcbur edir: hər bir ağac verilmiş növü bir və eyni ikili ağacla təmsil olunur ki, bu da bu müxtəlifliyi birmənalı şəkildə müəyyən edir. Üstəlik, yuxarıda göstərilən şərtləri yoxlayan hər bir işarələnmiş ikili ağac həqiqətən mövcud olan bir müxtəlifliyə uyğundur. Darvin hesab edir ki, o zaman müxtəlifliklərin sayını hesablamaq üçün hansısa riyazi alətdən istifadə etmək olardı, lakin bunun üçün kifayət qədər riyazi biliyi yoxdur.

İndi Darvinin işindən həqiqətən təsirləndiyiniz zaman, növbə sizindir: bu növün müxtəlifliklərinin sayını hesablamaq üçün bir proqram yazaraq onu təsirləndirin.

Giriş Məlumatları

Aşağıdakı sətirlərdən ibarətdir:

• birinci sətirdə: hər hansı bir ağacın inorder keçidi zamanı əldə edilən hündürlüklər ardıcıllığının n elementi;

• növbəti n sətir, hər biri bir tam ədəd olmaqla, millimetrlə hündürlüklərin ardıcıllığını təmsil edir.

Həm n, həm də hündürlük işarələri 0-dan böyük və ya bərabər və 1 000 000-dan kiçik və ya bərabərdir.

Çıxış Məlumatları

Ağac növlərinin sayını 1 000 000 007 moduluna görə bir tam ədəd olaraq çıxarın.