题目描述

因为驰驰不想写题意了，所以他假装自己需要做数学作业。

他告诉你数学作业总共有 $T$ 道题目，每道题目会给你 $n,m,k$。然后题目定义一个数列 $\{a_i\}$ 是好的，当且仅当序列 $\{b_i = a_i \land k\}$ 和 $\{c_i = a_i \lor k\}$ 都单调不减，并且 $0 \leq a_i \leq m$，其中 $\land,\lor$ 分别代表按位与和按位或运算。题目要求你求出好的数列的数量。

然后驰驰要假装自己不会做了，所以他要你帮他做作业。当然他会假装同情你，所以你只需要求出答案对 $998244353$ 取模的值。

输入格式

第一行一个正整数 $T$，表示题目数量。

接下来 $T$ 行，每行三个整数 $n,m,k$，表示一道题目。

输出格式

共 $T$ 行，每行一个整数表示问题的答案对 $998244353$ 取模的值。

3
2 2 2
3 4 6
5 12 13

5
22
1722

数据范围

• 对于 $30 \%$ 的数据，$n,m \leq 6,T \leq 10^3$；
• 对于另外 $30 \%$ 的数据，$m \leq 3$；
• 对于 $100 \%$ 的数据，$1 \leq T \leq 2 \times 10^5,1 \leq n < 2^{20}, 0 \leq m,k < 2^{20}$。