问题 5051 --挺好序列

5051: 挺好序列

题目描述

  如果一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ 满足 $\forall 1 \leq i \leq n,a_i | A$,则称这是一个挺好序列。
一个长度为 $n$ 的序列  $a_1, a_2, \cdots, a_n$  的价值为 $\gcd(a_1, a_2, \cdots, a_n, B)$,其中 $B$ 是定值。
对于一个固定的 $B$,定义 $f(x)$ 为 $A=x$ 时所有挺好序列的价值和。

$$\left(\sum_{i= 1}^m f(i)\right) \bmod 998244353$$

输入

一行三个正整数 $n,m,B$。

输出

一行一个整数表示答案。

样例输入输出

输入#1 复制
2 5 4
输出#1 复制
29

提示

子任务 ( 10分):$n,m,B \leq 5$;
子任务 ( 20分):$B=1$;
子任务 ( 30分):$m \leq 10^5$;
子任务 ( 40分):无特殊限制。
对于所有数据,$1 \leq n \leq 10^{18}$,$1 \leq m \leq 2 \times 10^7$,$1 \leq B \leq 10^{18}$。

序号 标题 作者 发表时间 费用 订购数 操作