D. Digit Sum Problem
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a nonnegative integer $$$x$$$, let $$$f(x)$$$ and $$$g(x)$$$ denote the digit sum of $$$x$$$ in binary and ternary, respectively.

Given $$$n, a, b, c$$$, compute $$$$$$\left(\sum_{i=1}^n a^i b^{f(i)} c^{g(i)} \right) \bmod 998244353.$$$$$$

Input

In the first line, $$$n, a, b, c$$$ ($$$1\leq n\leq 10^{13}, 1\leq a, b, c \lt 998244353$$$).

Output

One integer — the answer.

Examples
Input
123456 12345 234567 3456789
Output
664963464
Input
9876543210987 12816 837595 128478
Output
7972694