Problem description


Podzielność przez 37
(podzielnosc-37)
Memory limit: 128 MB
Time limit: 6.00 s

Jasio zapisał na tablicy całkiem dużą liczbę N. Zaczął się zastanawiać nad tym czy jest ona podzielna przez 37. Jasio niestety nie zna reguły podzielności przez 37, więc nie potrafi tego szybko stwierdzić. Chciałby Cię zapytać, ale się wstydzi, bo wydaje mu się, że powinien to wiedzieć i wyszedłby na głupiego. Dlatego postanowił zapytać o odrobinę trudniejszy problem, którego oczywiście także nie potrafi rozwiązać: ile jest różnych liczb podzielnych przez 37, które można uzyskać poprzez przestawienie kolejności cyfr w liczbie N? Taki problem wydaje mu się wystarczająco trudny, więc bez wahania zapytał Cię o jego rozwiązanie. Czy jesteś w stanie mu pomóc?

Napisz program, który: wczyta liczbę naturalną N, wyznaczy rozwiązanie problemu Jasia i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N – liczba, którą zapisał na tablicy Jasio.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – reszta z dzielenia przez 109 + 7 liczby różnych liczb podzielnych przez 37, które można uzyskać stosując pewne przestawienie cyfr w liczbie Jasia.

Uwaga

Jasio nie uznaje liczb z zerami wiodącymi za poprawne liczby.

Ograniczenia

1 ≤ N ≤ 10100.

Przykład

Input Output Explanation
148
3

Te liczby to oczywiście: 148, 481 oraz 814.