Kapitan Mambeks urządził grilla dla znajomych. Przygotował różnej długości patyczki do szaszłyków. Długość każdego patyczka wyraża się naturalną liczbą centymetrów. Na każdy patyczek można nadziać szaszłyk złożony z kawałków boczku albo cebuli, przy czym należy to zrobić tak, aby była zajęta cała długość patyczka. Każdy kawałek boczku ma długość 2 cm, a każdy kawałek cebuli - 1 cm. Nie ma żadnych ograniczeń co do stykających się ze sobą kawałków - kapitan może np. zrobić szaszłyk z samej cebuli. Jeden koniec każdego patyczka jest pomalowany gwiezdną farbą, więc np. szaszłyki boczek-boczek-cebula i cebula-boczek-boczek są różne.
Kapitan bardzo chciałby wiedzieć, ile różnych szaszłyków może nadziać na każdy patyczek i poprosił Cię o pomoc w obliczeniu tej liczby. Ponieważ jednak obawia się, że mogłaby się ona okazać bardzo duża, zadowoli się resztą z dzielenia jej przez 20062006.
Na przykład na patyczek o długości 4 cm można nadziać 5 różnych szaszłyków:
W pierwszym wierszu zapisana jest liczba patyczków. W kolejnych wierszach zapisane są długości kolejnych patyczków, wyrażone w centymetrach. Długość każdego patyczka jest liczbą całkowitą z przedziału [1, 109].
Program ma wypisać tyle wierszy, ile jest patyczków. W każdym wierszu ma się znaleźć reszta z dzielenia przez 20062006 liczby różnych szaszłyków, które można nadziać na dany patyczek.
2 3 4
3 5