Problem description

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Dominowanie (dominowanie) Memory limit: 32 MB Time limit: 0.50 s Dany jest prostokąt wymiaru 3 × 2N. Na ile sposobów można go ,,wydominować’’ – tj. pokryć kostkami domina wymiaru 1 × 2 pola, tak aby pokryć wszystkie pola, ale nie pokryć żadnego dwukrotnie? Poniżej przedstawiono przykładowe sposoby wydominowania dla N = 1. Napisz program, który: wczyta liczbę N, wyznaczy liczbę sposobów wydominowania planszy 3 × 2N i wypisze wynik na standardowe wyjście. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N. Wyjście Twój program powinien wypisać na wyjście dokładnie jedną liczbę całkowitą – resztę z dzielenia liczby sposobów pokrycia planszy kostkami domina przez 109 + 7. Ograniczenia 1 ≤ N ≤ 1018. Przykład Input Output 2 11