#PQJ932x4056. QOJ 932_4056

    ID: 3069 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2022枚举

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 。