题目大意
一个数是非回文数当且仅当不包含长度大于$1$的回文数。比如$16276$是无回文数,而$17276$因为含有$727$而不是。
求区间内有多少个非回文数。
小C有一个集合$S$,里面的元素都是小于$M$的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为$N$的数列,数列中的每个数都属于集合$S$。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数$x$,求所有可以生成出的,且满足数列中所有数的乘积$\bmod M$的值等于$x$的不同的数列的有多少个。小C认为,两个数列$\lbrace A_i\rbrace$和$\lbrace B_i\rbrace$不同,当且仅当至少存在一个整数$i$,满足$A_i\neq B_i$。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案$\bmod\,1004535809$的值就可以了。