Problem Description

Little D learned base conversion when he was two years old.

He wants to challenge you to find, for all numbers between $1$ and $n$, the sum of digits in both binary and ternary representations.

For a number $i$, let the sum of digits in binary and ternary be denoted as $a(i)$ and $b(i)$, respectively. For example, for $i = 114$, its binary representation is $(1110010)_2$ and its ternary representation is $(11020)_3$. Thus, $a(i)$ and $b(i)$ are both $4$.

Little D wants to know if you can correctly compute the base conversion for all numbers from $1$ to $n$. Therefore, he asks you to calculate $\sum\limits_{i = 1}^n x^i y^{a(i)} z^{b(i)}$, and since the answer can be very large, output the result modulo $998244353$.

Input Format

A single line containing four integers: $n, x, y, z$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

123456 12345 234567 3456789

Sample Output #1

664963464

Sample Input #2

1234567891 123 1 12345

Sample Output #2

517823355

Sample Input #3

9876543210987 1284916 83759265 128478129

Sample Output #3

115945104

Notes/Hints

Data Size and Constraints

This problem consists of 20 test cases.

• For test cases $1, 2, 3$, $n \leq 10^7$.
• For test cases $4, 5$, $x = y = 1$.
• For test cases $6, 7$, $y = 1$.
• For test cases $8, 9, 10$, $n < 10^{10}$.
• For test cases $11, 12, 13, 14$, $n \leq 5 \times 10^{11}$.

For all test cases, $1 \leq n \leq 10^{13}$, and $1 \leq x, y, z < 998244353$.

见题面 Input 部分

见题面 Output 部分