小 D 两岁的时候就学会了进制转换。
所以他想问你,对于所有 1∼n 之间的数,这个数在二进制和三进制下的数位和分别是多少。
对于 i,记二进制和三进制的数位和分别为 a(i) 和 b(i)。比如对于一个数 i=114,那么它二进制表示为 (1110010)2,三进制表示为 (11020)3,那么 a(i) 和 b(i) 分别为 4 和 4。
小 D 想知道你是不是真的能算对 1 到 n 里面所有数进制转换,所以想问你 ∑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,3,n≤107。
对于测试点 4,5,x=y=1。
对于测试点 6,7,y=1。
对于测试点 8,9,10,n≤1010。
对于测试点 11,12,13,14,n≤5×1011。
对于所有测试点,1≤n≤1013,1≤x,y,z<998244353。