Top Boya#3376
Masanın üzərində 2N ağ top iki sırada yerləşdirilib və bu toplar gözəl bir 2-yə-N düzbucaqlı əmələ gətirir. Jonun böyük bir qara boya dolu vedrəsi var. (Niyə olduğunu soruşmayın.) O, bütün topları qara rəngə boyamaq istəyir, amma bunu edərkən bir az riyazi əyləncə yaşamaq istəyir. (Yenə də niyə olduğunu soruşmayın.) Əvvəlcə, bütün topları qara rəngə boyamağın fərqli yollarının sayını hesabladı. Tez bir zamanda, cavabın (2N)! olduğunu anladı və bunun çox asan olduğunu düşündü. Beləliklə, problemi daha maraqlı etmək üçün bəzi qaydalar təqdim etdi.
Jonun boyadığı ilk top 2N toplardan hər hansı biri ola bilər.
Bundan sonra, boyadığı hər növbəti top artıq boyanmış qara topa bitişik olmalıdır. İki top üfüqi, şaquli və ya diaqonal olaraq bir-birinə bitişik sayılır.
Jon qaydalardan çox məmnun qaldı, buna görə də topları bu qaydalara uyğun boyamağın yollarının sayını saymağa başladı. Siz Jon-dan daha sürətli cavabı tapa biləcək bir proqram yaza bilərsinizmi?
Giriş bir neçə test halından ibarətdir. Hər test halı N tam ədədini ehtiva edən bir sətirdən ibarətdir, burada 1 ≤ N ≤ 1000. Giriş N = 0 olan bir sətirlə bitir.
Hər test halı üçün, Jonun bütün 2N topları qaydalara uyğun boyaya biləcəyi mümkün yolların sayını ehtiva edən bir sətir çap edin. Say çox böyük ola bilər, buna görə sayın 1000000007 modulu ilə çap edin.
Nümunə 1