Exponential Weighted Digit Sums

Given four integers (n), (x), (y) and (z). For each integer (i) with (1 \le i \le n), let (a(i)) be the digit sum of (i) in its binary representation and (b(i)) be the digit sum of (i) in its ternary representation. For example, for (i=114), its binary representation is ((1110010)_2) so that (a(114)=4) and its ternary representation is ((11020)_3) so that (b(114)=4).

The task is to compute the sum [ S = \sum_{i=1}^n x^i ; y^{a(i)} ; z^{b(i)} \mod 998244353, ] and output the result modulo (998244353).

inputFormat

The input consists of a single line containing four space-separated integers: (n), (x), (y), and (z).

outputFormat

Output a single integer which is the value of (S) modulo (998244353).

sample

1 1 1 1

1