#6247. 九个太阳

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Sdchr

题目描述

在遥远的苏远山上,yww 自诩为太阳。

yww 对其他自以为是太阳的人很敌视,他决定通过发出光芒来教化这些人。当 yww 的光芒照耀到一个人的身上时,这个人就会在这股古老而强大的力量的压迫下,双膝跪地,双手平举,随后身体前俯后仰,手也跟着摆动,并大声喊道:「yww 是我们的红太阳!」。

除了 yww 以外,苏远山上一共有 n 个自以为是太阳的人。由于 yww 具有某种神秘力量,一次教化的人数只能是正整数 K 的倍数,且 K 2 的幂。

yww 想知道,如果他发出光芒,被教化的人有多少种情况。两种情况视作不同,当且仅当存在一个人,在一种情况中被教化,在另外一种情况中没有被教化。由于情况实在太多了,所以答案为 998244353 取模。

**一句话题意:**给定 n, K ,满足 K 2 的幂,求

\begin{aligned} \sum_{K | i, 0 \le i \le n} \binom{n}{i} \end{aligned}

998244353 取模。

输入格式

第一行两个正整数 n, K

输出格式

输出一行答案。

样例

样例输入

5 2

样例输出

16

数据范围与提示

对于 30\% 的数据, 1 \le n \le 100, 1 \le K \le 2 ^ 6
对于 100\% 的数据, 1 \le n \le {10} ^ {15}, 1\le K \le 2 ^ {20} ,且 K 2 的幂。