Dana jest liczba całkowita $N$ zapisana w systemie dziesiętnym.
Rozważmy wszystkie liczby całkowite, które można utworzyć poprzez przestawienie cyfr liczby $N$ w taki sposób, aby otrzymana liczba nie miała zer wiodących.
Znajdź liczbę takich liczb całkowitych, które są podzielne przez $11$, modulo $2147483647$ ($= 2^{31} - 1$), co jest liczbą pierwszą.
Zauważ, że liczby całkowite utworzone poprzez przestawienie cyfr liczby $N$ obejmują również samą liczbę $N$.
Wejście
Wejście podawane jest w następującym formacie:
$$N$$
- Wszystkie wartości na wejściu są liczbami całkowitymi.
- $1 \le N < 10^{2 \times 10^6}$
- Liczba $N$ podana jest w zapisie dziesiętnym bez zer wiodących.
Wyjście
Wypisz odpowiedź w jednym wierszu.
Przykłady
Wejście 1
1001
Wyjście 1
2
Wejście 2
31415926535
Wyjście 2
144000
Uwaga
W pierwszym przykładzie warunek spełniają liczby $1100$ oraz $1001$.