Problem description

Jaś jest miłośnikiem łamigłówek. Całe biurko ma zagracone różnymi, skomplikowanymi zagadkami. Nadszedł jednak dzień, w którym Jaś był na tyle zmęczony ich rozwiązywaniem, że postanowił poukładać różne kształty z zapałek.

Niestety, Jaś nie byłby Jasiem, gdyby nie odezwała się w nim jego matematyczna natura. Postanowił sprawdzić ile różnych nieujemnych liczb całkowitych podzielnych przez 111 jest w stanie ułożyć z co najwyżej N zapałek. Jaś dosyć szybko poradził sobie z tym zadaniem, jednak chciałby przekonać się o poprawności swoich wyników. Czy jesteś w stanie mu pomóc?

Każda liczba składa się z ciągu cyfr (bez zer wiodących). Na poniższym rysunku pokazano jak za pomocą zapałek skonstruować każdą z cyfr od 0 do 9 oraz jak wyglądają dwie liczby podzielne przez 111, skonstruowane z 6 zapałek.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba całkowita N, będąca liczbą zapałek posiadanych przez Jasia.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą, będącą liczbą liczb podzielnych przez 111, możliwych do ułożenia z co najwyżej N zapałek.

Ograniczenia

1 ≤ N ≤ 20.

Przykłady

5

0

6

2

10

3