Þér er gefin heiltala $N$ í tugakerfi.
Skoðum allar heiltölur sem hægt er að mynda með því að endurraða tölustöfum $N$ þannig að talan sem fæst hafi engin fremri núll (leading zeros).
Finndu fjölda slíkra heiltalna sem eru deilanlegar með $11$, modulo $2147483647$ ($= 2^{31} - 1$), sem er frumtala.
Athugaðu að heiltölurnar sem myndast við að endurraða tölustöfum $N$ innihalda $N$ sjálfa.
Inntak
Inntakið er gefið á eftirfarandi sniði:
$$N$$
- Öll inntaksgildi eru heiltölur.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ er gefin í tugakerfi án fremri núlla.
Úttak
Prentaðu svarið á einni línu.
Dæmi
Inntak 1
1001
Úttak 1
2
Inntak 2
31415926535
Úttak 2
144000
Athugasemd
Í fyrsta dæminu uppfylla $1100$ og $1001$ skilyrðið.