QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[0]

# 4056. 进制转换

Statistics

小 D 两岁的时候就学会了进制转换。

所以他想问你,对于所有 1n 之间的数,这个数在二进制和三进制下的数位和分别是多少。

对于 i,记二进制和三进制的数位和分别为 a(i)b(i)。比如对于一个数 i=114,那么它二进制表示为 (1110010)2,三进制表示为 (11020)3,那么 a(i)b(i) 分别为 44

小 D 想知道你是不是真的能算对 1n 里面所有数进制转换,所以想问你 ni=1xiya(i)zb(i) 是多少。由于答案很大,输出答案对 998244353 取模的结果。

输入格式

一共一行,包含四个整数 n,x,y,z

输出格式

输出一个数,表示答案。

样例数据

样例 1 输入

123456 12345 234567 3456789

样例 1 输出

664963464

样例 2 输入

1234567891 123 1 12345

样例 2 输出

517823355

样例 3 输入

9876543210987 1284916 83759265 128478129

样例 3 输出

115945104

子任务

一共 20 个测试点。

对于测试点 1,2,3n107

对于测试点 4,5x=y=1

对于测试点 6,7y=1

对于测试点 8,9,10n1010

对于测试点 11,12,13,14n5×1011

对于所有测试点,1n10131x,y,z<998244353