配点 : 600 点
問題文
回答以下问题 f(K) 。
(1,2,\ldots,K) 的排列 给出了 P=(P_{1},P_{2}, \ldots ,P_{K}) 。 P 满足以下所有条件时, 类似堆 我们称之为排列。
2P_{i} \leq P_{2i} \left(1 \leq i \leq \left\lfloor \frac{K}{2} \right\rfloor \right)
2P_{i} \leq P_{2i+1} \left(1 \leq i \leq \left\lfloor \frac{K-1}{2} \right\rfloor \right)
求类堆排列的数量。
N ,所以 f(1)+f(2)+ \cdots +f(N) 该值应乘以 998244353 除以求余。
1 每个输入的测试用例是 有 T 件。
制約
- 1 \leq T \leq 10^{6}
- 1 \leq N \leq 10^{18}
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}
每个测试用例均按以下格式给出。 打印
N
出力
T 行。 i 在线 i 个测试用例的答案。
入力例 1
3 6 1 1000
出力例 1
9 1 465040340
例如 第 K=5 时, P=\lbrace 1,2,3,5,4 \rbrace 是一个类似堆的排列。 01