#Lutece2623. 奥日与失落走廊

奥日与失落走廊

Migrated from Lutece 2623 奥日与失落走廊

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

『朦胧的迷雾森林蒙蔽所有人的心智』

『迷路之人再不能重见天日』

pic1  \space


 \space

随着氤氲灯笼被点燃,迷雾渐渐散去,迷雾森林的神秘面纱终于揭开。现在,迷雾森林的真面目就那么暴露无遗地展现在了奥日眼前,那是一座宏伟的走廊——失落走廊。

通过观察奥日发现,失落走廊的构造十分特别。具体来说,失落走廊由 nn 个站点构成,编号为 1n1\ldots n。第 ii 个站点与所有编号为 ii 因数的站点 jj(包括 ii 本身)都有着一条由 ii 通向 jj 的单向道路。奥日可以从 1n1\ldots n 中的任意一个站点进入失落走廊,但只能从 11 号站点逃离失落走廊。每经过一条单向道路,奥日就要消耗一格能量,进入走廊和逃离走廊不需要能量。

奥日现在只有 kk 格能量,你可以帮奥日计算出他可以有多少种不同的探索路线可以选择吗?

两条路线不同即经过的站点序列不同。

Input

输入一行两个整数 n,kn,k

Output

输出一行一个整数,表示答案对 998244353998244353 取模的结果。

Samples

3 2
5
10 5
136
2333 233
651531176
1145141919 810
251345645

Constraints

1n1011,1k1061\le n\le 10^{11},1\le k\le 10^6

Note

对于样例一,奥日可以探索的所有的 55 条路径为:

  • 3,3,13,3,1
  • 3,1,13,1,1
  • 2,2,12,2,1
  • 2,1,12,1,1
  • 1,1,11,1,1

Resources

2021 UESTC ICPC Training for Math and Geometry