You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 最近在研究组合数学，他学会了如何枚举排列。

小 Z 最近在研究数论，他学会了求最大公约数。

于是小 Y 和小 Z 联手出了一个有趣的题目：

有多少个长度为 $n$ 且任意相邻两个数的最大公约数都不为 $k$ 的排列？

然而他们并不会做这个题，所以请你来帮帮他们吧！

输入格式

从 permutation.in 文件读入数据。

​一行两个整数 $n,k$ ，由一个空格隔开，含义如上文题面所示。

输出格式

输出到 permutation.out 文件。

​一个整数，表示满足条件的排列数量对 $998244353$ 取模后的结果。

样例

3 2

6

满足条件的排列如下：$\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}$ ，共 $6$ 种。

2999 391

691177047

数据范围

对于全部测试数据，满足 $1\leq n\leq 3000,1\leq \frac{n}{k}\leq10$ 。