Ti viene dato un intero $N$ rappresentato in base decimale.
Considera tutti gli interi che possono essere formati riordinando le cifre di $N$ in modo tale che il numero risultante non abbia zeri iniziali.
Trova il numero di tali interi che sono divisibili per $11$, modulo $2147483647$ ($= 2^{31} - 1$), che è un numero primo.
Nota che gli interi formati riordinando le cifre di $N$ includono $N$ stesso.
Input
L'input viene fornito nel seguente formato:
$$N$$
- Tutti i valori in input sono interi.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ è dato in base decimale senza zeri iniziali.
Output
Stampa la risposta su una singola riga.
Esempi
Input 1
1001
Output 1
2
Input 2
31415926535
Output 2
144000
Note
Nel primo esempio, $1100$ e $1001$ soddisfano la condizione.