Subset Sum Divisibility

We define the function \(F(x,a,b)\) by

\[ F(x,a,b) = \begin{cases} 0, &\text{if }a=0 \text{ or } b=0, \\ \gcd(x^a-1,x^b-1)+1, & x>0,\end{cases} \]

In particular, when \(a=0\) or \(b=0\), we set \(F(x,a,b)=0\).

You are given five nonnegative integers \(m, a, b, c, d\). Define

[ L = F(m,a,b) + 1, \quad R = F(m,c,d). ]

Consider the set \(S = \{L, L+1, L+2, \dots, R\}\). (Note that if \(R < L\) then \(S\) is empty.)

Your task is to count the number of subsets of \(S\) whose sum is a multiple of \(m\). The empty subset is considered and its sum is \(0\). Because the answer might be large, output it modulo \(998244353\).

Note: For nonzero \(a, b\) one may prove that \(\gcd(m^a-1, m^b-1)=m^{\gcd(a,b)}-1\), and hence in that case \(F(m,a,b)=m^{\gcd(a,b)}\). However, if either \(a=0\) or \(b=0\) then \(F(m,a,b)=0\>.

inputFormat

The input consists of a single line containing five nonnegative integers:

m a b c d

It is guaranteed that \(m\) is positive (i.e. \(m\ge 1\)).

outputFormat

Output a single integer: the number of subsets of \(S\) whose sum is divisible by \(m\), taken modulo \(998244353\).

sample

5 2 3 1 2

1