Problem description

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 10⁹ + 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 ≤ 10¹⁰⁰.

Przykład

148

3