UOJ Logo Universal Online Judge

UOJ

附件下载 统计

在跳蚤国,一位名叫跳蚤比克的贤者发现了一个奇妙的函数 f(x),是一种「跳蚤魔力函数」。「跳蚤魔力函数」满足 f(1)=1 且对于任意 p,q 使得 gcd(p,q)=1,都有 f(pq)=f(p)f(q)。此外,在质数 pk 次幂处,它的点值恰好等于一个华丽的二次函数 w(pk)。在跳蚤国的历史上,这个函数曾经被古老的智慧封存起来,直到跳蚤比克的发现。

在定都仪式的阅兵会上,跳蚤国的领导者们决定利用这个函数来增强国家的魔力。于是,在跳蚤国的红色广场上,一群跳蚤兵被精心地排列成了一个巨大的 n×n 矩阵。每一只跳蚤都蕴含着一定的魔力,而这个魔力的值取决于它所处的位置。更为具体地,第 i 行第 j 列的跳蚤拥有着 f(ij) 的魔力。

跳蚤国王想要知道如何计算所有跳蚤产生的魔力值之和。但是一个一个数过去太慢了,所以跳蚤国王需要你的帮助。为了不为难你,你只需要求出答案对 998244353 取模后的结果就行了。

输入格式

一行四个非负整数 n,w0,w1,w2。其中 w(x)=w0+xw1+x2w2

输出格式

一行一个整数,表示答案对 998244353 取模后的结果。

样例一

input

12 3 2 1

output

1239814

样例二 样例五

见下发文件。

限制与约定

  • Subtask 1(5 points):保证 n103
  • Subtask 2(25 points):保证 n3×104
  • Subtask 3(15 points):保证 n106
  • Subtask 4(25 points):保证 n3×107
  • Subtask 5(10 points):保证 n108
  • Subtask 6(15 points):保证 n3×108
  • Subtask 7(5 points):无特殊限制。

对于所有数据,保证 1n1090w0,w1,w2<998244353

时间限制:6s

空间限制:1024MB