P8350 [SDOI/SXOI2022] Base Conversion

When Little D was two years old, he already learned base conversion. So he wants to ask you: for all numbers between $1 \sim n$, what are the sums of digits of this number in binary and ternary, respectively. For $i$, let the sums of digits in binary and ternary be $a(i)$ and $b(i)$, respectively. For example, for $i = 114$, its binary representation is $(1110010)_2$, and its ternary representation is $(11020)_3$, so $a(i)$ and $b(i)$ are both $4$. Little D wants to know whether you can really compute base conversions correctly for all numbers from $1$ to $n$, so he asks what $$\sum\limits_{i = 1}^n x^i y^{a(i)} z^{b(i)}$$ is. Since the answer is very large, output the result modulo $998244353$.

There is only one line with four integers, in order: $n, x, y, z$.

Output one line with one integer, representing the answer.

### Constraints This problem has $20$ test points. - For test points $1,2,3$, $n \le 10^7$. - For test points $4,5$, $x = y = 1$. - For test points $6,7$, $y = 1$. - For test points $8,9,10$, $n < 10^{10}$. - For test points $11,12,13,14$, $n \le 5 \times 10^{11}$. For all test points, $1 \le n \le 10^{13}$, $1 \le x, y, z < 998244353$. Translated by ChatGPT 5