#PQJ932x4056. QOJ 932_4056
QOJ 932_4056
小 D 两岁的时候就学会了进制转换。
所以他想问你,对于所有 1 ∼ 𝑛 之间的数,这个数在二进制和三进制下的数位和分别是多少。
对于 𝑖 ,记二进制和三进制的数位和分别为 𝑎 ( 𝑖 ) 和 𝑏 ( 𝑖 ) 。比如对于一个数 𝑖
114 ,那么它二进制表示为 ( 1110010 ) 2 ,三进制表示为 ( 11020 ) 3 ,那么 𝑎 ( 𝑖 ) 和 𝑏 ( 𝑖 ) 分别为 4 和 4 。
小 D 想知道你是不是真的能算对 1 到 𝑛 里面所有数进制转换,所以想问你 ∑ 𝑖
1 𝑛 𝑥 𝑖 𝑦 𝑎 ( 𝑖 ) 𝑧 𝑏 ( 𝑖 ) 是多少。由于答案很大,输出答案对 998 244 353 取模的结果。
输入格式
一共一行,包含四个整数 𝑛 , 𝑥 , 𝑦 , 𝑧 。
输出格式
输出一个数,表示答案。
样例数据 样例 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 , 𝑛 ≤ 10 7 。
对于测试点 4 , 5 , 𝑥
𝑦
1 。
对于测试点 6 , 7 , 𝑦
1 。
对于测试点 8 , 9 , 10 , 𝑛 ≤ 10 10 。
对于测试点 11 , 12 , 13 , 14 , 𝑛 ≤ 5 × 10 11 。
对于所有测试点, 1 ≤ 𝑛 ≤ 10 13 , 1 ≤ 𝑥 , 𝑦 , 𝑧 < 998 244 353 。