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; } Liczba wzorów (liczba-wzorow) Memory limit: 64 MB Time limit: 1.00 s Krzysiu w ramach prezentu urodzinowego dostał nowiutką, podłużną planszę złożoną z 2 × N kwadratów. Każdy kwadrat ma dwie strony - białą i czarną. Krzysiu bawi się odwracając różne kwadraty, tworząc rozmaite wzory. Szczególnie podobają mu się takie, w których czarne kwadraty tworzą spójny obszar, oraz w których w każdej kolumnie występuje co najmniej jeden czarny kwadrat. Teraz Krzysiu zastanawia się, na ile sposobów może ułożyć wzory, które spełniają powyższe wymagania? Wejście W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca długość planszy Krzysia. Wyjście W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę naturalną, oznaczającą liczbę możliwych wzorów, które spełniają wymagania Krzysia. Liczba może być duża, dlatego należy wypisać jej resztę z dzielenia przez 109 + 7. Ograniczenia 1 ≤ N ≤ 1 000 000. Przykład Input Output 2 7