Little D learned how to perform base conversions when he was two years old.

Therefore, he wants to ask you, for all numbers between $1$ and $n$, what are the sums of their digits in binary and ternary representations, respectively.

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

Little D wants to know if you can really calculate the base conversions for all numbers from $1$ to $n$, so he wants to ask you for the value of $\sum_{i=1}^n x^iy^{a(i)}z^{b(i)}$. Since the answer can be very large, output the result modulo $998\,244\,353$.

Input

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

Output

Output a single integer representing the answer.

Examples

Input 1

123456 12345 234567 3456789

Output 1

664963464

Input 2

1234567891 123 1 12345

Output 2

517823355

Input 3

9876543210987 1284916 83759265 128478129

Output 3

115945104

Subtasks

There are $20$ test cases in total.

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 \leq 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 < 998\,244\,353$.