시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 25 | 3 | 3 | 12.000% |
Aby wybudować Kanał Panamski potrzeba było 20 milionów godzin ludzkiej pracy. Tymczasem w samym tylko 2003 roku na całym świecie przez 9 miliardów godzin ludzie układali komputerowego Pasjansa. Niestety nie wiemy, ile czasu ludzkość poświęciła grze Tetris. Kierując się, jednak, swoim doświadczeniem w tym temacie, sądzimy, że również bardzo dużo...
Dana jest prostokątna plansza o szerokości czterech pól i wysoko- ści n pól. Dany jest stan pól pierwszego wiersza planszy. Mamy do dyspozycji 7 różnych typów klocków (patrz rysunek) dowolną liczbę klocków każdego typu. Są to klocki używane zwykle w grze Tetris. Należy jednak zwrócić uwagę, że klocek „długi” zajmuje trzy pola, a nie cztery. Klocki wolno obracać. Na ile różnych sposobów można całkowicie pokryć planszę klockami?
W pierwszej linii znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę testów.
Pierwsza linia testu zawiera liczbę n (1 ≤ n ≤ 109), określającą wysokość planszy. W drugiej linii znajdują się 4 znaki (’*’ lub ’.’), określające stan pierwszego wiersza planszy. ’*’ oznacza pole pokryte, a ’.’ pole wolne.
Dla każdego testu oblicz liczbę różnych sposobów całkowitego pokrycia planszy przy pomocy dostępnych klocków. Wypisz resztę z dzielenia tej liczby przez 106.
4 2 **** 2 .... 2 *... 1 *...
0 3 1 1