A good sequence a0, a1, ..., atn−1 satisfies following criteria: • a0 = 0, atn−1 = 2tn − 1, 1 ≤ ak+1 − ak ≤ d (0 ≤ k < tn − 1). • ∀ i, j, aj − ai ̸= kn (k is any odd number, 0 ≤ i < j < tn). F wants to know the number of good sequence.
输入格式
The first line contains integer T (1 ≤ T ≤ 104) — the number of test cases. The first line of each test case contains three integers t, n, d (1 ≤ d ≤ 5·104, 1 ≤ t ≤ 105, 1 ≤ n ≤ 1015). It is guaranteed that the sum of d does not exceed 2 · 105.
输出格式
For each case, output the number of good sequence modulo 998244353.