#P18631. Digit Sum Problem

Digit Sum Problem

Digit Sum Problem

对于非负整数 xx,令 f(x)f(x) 和 g(x)g(x) 分别表示 xx 的二进制数位和与三进制数位和。

给定 n,a,b,cn,a,b,c,计算

$$\left(\sum_{i=1}^{n}a^i b^{f(i)}c^{g(i)}\right)\bmod998244353.$$

输入格式

一行四个整数 n,a,b,cn,a,b,c。

输出格式

输出一个整数,表示所求结果。

数据范围

1≤n≤10131\le n\le10^{13},1≤a,b,c<9982443531\le a,b,c<998244353。

样例输入 1

123456 12345 234567 3456789

样例输出 1

664963464

样例输入 2

9876543210987 12816 837595 128478

样例输出 2

7972694