Gegeben ist eine ganze Zahl $N$ in Dezimaldarstellung.
Betrachte alle ganzen Zahlen, die durch Umordnen der Ziffern von $N$ gebildet werden können, sodass die entstehende Zahl keine führenden Nullen hat.
Bestimme die Anzahl solcher ganzer Zahlen, die durch $11$ teilbar sind, modulo $2147483647$ ($= 2^{31} - 1$), was eine Primzahl ist.
Beachte, dass zu den durch Umordnen der Ziffern von $N$ gebildeten ganzen Zahlen auch $N$ selbst gehört.
Eingabe
Die Eingabe erfolgt im folgenden Format:
$$N$$
- Alle Eingabewerte sind ganze Zahlen.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ wird in Dezimaldarstellung ohne führende Nullen angegeben.
Ausgabe
Gib die Antwort in einer einzigen Zeile aus.
Beispiele
Eingabe 1
1001
Ausgabe 1
2
Eingabe 2
31415926535
Ausgabe 2
144000
Hinweis
Im ersten Beispiel erfüllen $1100$ und $1001$ die Bedingung.