Cel
Zadanie na obliczenia iteracyjne (wymaga użycia cyklicznej tablicy).

Problem
Mamy ciąg liczbowy a_n zadany następującymi warunkami:

• a₀ = 1,
• a_i = a_i-1 + 2a_i-2 + ... + i a₀ dla 0 < i < 20,
• a_i = (a_i-1 + 2a_i-2 + ... + 20a_i-20) mod 10⁷ dla i > 19

(gdzie "mod" oznacza resztę z dzielenia).

Zadanie
Napisz program, który będzie wyliczał zadany element podanego powyżej ciągu.
Jako daną wejściową program wczytuje pojedynczą liczbę całkowitą nieujemną będącą indeksem elementu ciągu, którego wartość ma zostać wyliczona.
Zwracana ma być pojedyncza liczba całkowita będąca wartością tego elementu.
Uwaga: Program ma nałożone w miarę rygorystyczne ograniczenia odnośnie limitu używanej pamięci.

Przykład
Wejście

20000000

Wyjście

2291660

Przykłady

Wejście	Wyjście
1	1
10	6765
10000000	3349246