#6718. 九个太阳「弱」化版

题目描述

2020/05/25 14:14 更新：数据已修复

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

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

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

yww 想知道，如果他发出光芒，被教化的人有多少种情况。两种情况视作不同，当且仅当存在一个人，在一种情况中被教化，在另外一种情况中没有被教化。由于答案可能很大，所以你只需要输出答案对 998244853 取模。

\sum_{K \mid i, 0 \leq i \leq n} \binom{n}{i}

对 998244853 取模。

第一行两个正整数 $n, K$ 。

输出一行答案。

输入

5 2

输出

对于 30% 的数据， $1 \leq n \leq 100, 1 \leq K \leq 2^6$ ；

对于 100% 的数据， $1 \leq n \leq 10^{15}, 1 \leq K \leq 2^{15}$ ，且 $K$ 为 2 的幂。

请注意常数因子带来的程序效率上的影响。