Sequence Product Modulo Count

Given a set \( S = \{0, 1, \ldots, m-1\} \) and a sequence generator that produces sequences of length \( n \) where each element is chosen from \( S \), count the number of distinct sequences such that the product of all elements modulo \( m \) equals a given integer \( x \). Two sequences are considered different if there exists an index \( i \) such that \( A_i \neq B_i \). Since the answer can be very large, output it modulo \( 1004535809 \).

Input: Three integers \( m \), \( n \), and \( x \) separated by spaces.

Output: A single integer representing the number of sequences satisfying the condition, taken modulo \( 1004535809 \).

inputFormat

The input consists of a single line with three integers \( m \), \( n \), and \( x \) ( \( 0 \le x < m \) ), separated by spaces.

outputFormat

Output a single integer: the count of sequences whose product modulo \( m \) equals \( x \), modulo \( 1004535809 \).

sample

5 2 0

9