Sequence Counts with Specified GCD and LCM

You are given three positive integers: n, x and y. Find the number of different sequences \((a_1,a_2,\cdots,a_n)\) such that:

• The greatest common divisor (\(\gcd(a_1,a_2,\cdots,a_n)\)) equals \(x\).
• The least common multiple (\(\operatorname{lcm}(a_1,a_2,\cdots,a_n)\)) equals \(y\).

Two sequences are considered different if there exists at least one index \(i\) such that \(a_i\) in the first sequence is different from \(a_i\) in the second sequence.

If \(y\) is not divisible by \(x\), then no valid sequence exists. Otherwise, let \(m=\frac{y}{x}\) and express its prime factorization as \[ m=\prod_{i=1}^{k}p_i^{e_i}. \] For each prime \(p_i\), suppose we choose exponents \(b_1,b_2,\ldots,b_n\) for \(a_1,x\) such that after writing \(a_j=x\cdot p_i^{b_j}\) (with \(0\le b_j\le e_i\)), the following conditions hold:

• \(\min\{b_1,b_2,\ldots, b_n\}=0\) (ensuring \(x\) divides the \(\gcd\)).
• \(\max\{b_1,b_2,\ldots,b_n\}=e_i\) (ensuring \(y\) is the \(\operatorname{lcm}\)).

For each prime the number of valid assignments is given by inclusion‐exclusion as follows (if \(e_i\ge1\)): \[ F(e_i)= (e_i+1)^n - 2\,e_i^n + (e_i-1)^n. \]

If \(e_i=0\) then note the factor is 1. The final answer is the product of \(F(e_i)\) over all prime factors of \(m\), taken modulo \(998\,244\,353\).

inputFormat

The input consists of a single line containing three integers \(n\), \(x\) and \(y\) (\(1 \le n \le 10^5\), \(1 \le x,y \le 10^{12}\)).

outputFormat

Output a single integer representing the number of valid sequences modulo \(998\,244\,353\).

sample

1 1 1

1