Se te da un entero $N$ representado en base decimal.
Considera todos los enteros que se pueden formar reordenando los dígitos de $N$ de tal manera que el número resultante no tenga ceros a la izquierda.
Encuentra el número de tales enteros que son divisibles por $11$, módulo $2147483647$ ($= 2^{31} - 1$), que es primo.
Ten en cuenta que los enteros formados al reordenar los dígitos de $N$ incluyen al propio $N$.
Entrada
La entrada se proporciona en el siguiente formato:
$$N$$
- Todos los valores de entrada son enteros.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ se da en decimal sin ceros a la izquierda.
Salida
Imprime la respuesta en una sola línea.
Ejemplos
Entrada 1
1001
Salida 1
2
Entrada 2
31415926535
Salida 2
144000
Nota
En el primer ejemplo, $1100$ y $1001$ satisfacen la condición.