Problem Description

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

is. Since the answer is very large, output the result modulo $998244353$.

Input Format

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

Output Format

Output one line with one integer, representing the answer.

123456 12345 234567 3456789

664963464

1234567891 123 1 12345

517823355

9876543210987 1284916 83759265 128478129

115945104

Hint

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