小 C 有一个集合 ，里面的元素都是小于 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 的数列，数列中的每个数都属于集合 。

小 C 用这个生成器生成了许多这样的数列。但是小 C 有一个问题需要你的帮助：给定整数 ，求所有可以生成出的，且满足数列中所有数的乘积 modM 的值等于 的不同的数列的有多少个。小 C 认为，两个数列 和 不同，当且仅当至少存在一个整数 ，满足 。另外，小 C 认为这个问题的答案可能很大，因此他只需要你帮助他求出答案 mod1004535809 的值就可以了。