问题 D: 小凯爱数学

内存限制：512 MB 时间限制：5 S

题面：传统评测方式：文本比较上传者：

提交：2 通过：1

给定两个整数 n 和 m
考虑序列[1,2,3,…,n] 的所有非空子集。返回满足以下条件的子集 A 的数量：该子集 A 的元素S=∑_x∈Ax 满足 S≡0(modm)。
最终结果对 998244353 取模。

多组数据，第一行一个整数 1≤T≤5 表示有 T 组数据。
每组数据第一行两个整数n,m满足1≤n≤10 18， 2≤m≤200

每行输出一个整数，代表子集个数对 998244353 取模后的结果

11
255
577613259

样例解释当 n=5,m=3 时，一共有11个非空子集满足子集和为3的倍数[1,2] [1,2,3] [1,2,3,4,5] [1,2,4,5] [1,3,5] [1,5] [2,3,4] [2,4] [3] [3,4,5] [4,5]