On vous donne un entier $N$ représenté en base dix.
Considérez tous les entiers qui peuvent être formés en réarrangeant les chiffres de $N$ de telle sorte que le nombre résultant n'ait pas de zéros non significatifs en tête.
Trouvez le nombre de tels entiers qui sont divisibles par $11$, modulo $2147483647$ ($= 2^{31} - 1$), qui est un nombre premier.
Notez que les entiers formés en réarrangeant les chiffres de $N$ incluent $N$ lui-même.
Entrée
L'entrée est donnée sous le format suivant :
$$N$$
- Toutes les valeurs en entrée sont des entiers.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ est donné en écriture décimale sans zéros en tête.
Sortie
Affichez la réponse sur une seule ligne.
Exemples
Entrée 1
1001
Sortie 1
2
Entrée 2
31415926535
Sortie 2
144000
Note
Dans le premier exemple, $1100$ et $1001$ satisfont la condition.