İnək gimnastlar

Ferma həyatından yorulan inəklər bütün əmlaklarını satıb səyyar sirk truppasına qoşuldular. İndiyədək inəklərə sadə nömrələr düşürdü: məşəllərlə jonqlyorluq, kanat üzərində gəzmə, təkərli velosipedlə sürmə — çevik bir inəyin öhdəsindən gələ bilməyəcəyi heç nə yox idi. Lakin sirk direktoru növbəti tamaşa üçün çox daha effektli bir nömrə hazırlamaq istəyir.

Yeni nömrə üçün səhnə dairə şəklində yerləşdirilmiş $n$ platformadan ibarətdir. Hər platformada $1$-dən $n$-ə qədər inək bir-birinin üstünə qalxaraq qüllə əmələ gətirməlidir. Direktorun siqnalı ilə bütün qüllələr eyni zamanda saat əqrəbi istiqamətində yıxılmalıdır: qüllənin ən aşağısındakı inək öz yerində qalır, onun üstündəki inək saat əqrəbi istiqamətində bir platforma irəli hərəkət edir, növbəti inək isə iki platforma irəli və s. Təcrübəli gimnastkalar olduqları üçün inəklər nömrənin texniki tərəfinin öhdəsindən gələ biləcəklərinə əmindirlər. Yıxılarkən qüllələr bir-birinə mane olmur, buna görə də hər inək ona nəzərdə tutulmuş platformaya enir. Eyni platformaya enən bütün inəklər yeni bir qüllə əmələ gətirir ki, bu qüllə artıq yıxılmır.

Direktor hesab edir ki, əgər yıxılmadan sonra hər platformadakı yeni qüllə həmin platformadakı ilkin qüllədə olduğu qədər inək saxlayırsa, nömrə xüsusilə effektli olacaq. Əgər qüllələrin hündürlük konfiqurasiyası bu şərti ödəyirsə, onu sehrli adlandıraq. İnəklərə sehrli konfiqurasiyaların sayını hesablamaqda kömək edin. Bu ədəd çox böyük ola biləcəyindən, onu 10^9 + 7 modulu üzrə çap edin.

Əgər heç olmasa bir platformada fərqli sayda inək varsa, iki konfiqurasiya fərqli hesab olunur.