#215770. [JAG 2023 Summer Camp #2] Distance Permutation

You construct a permutation of length in the following way.

The number line has points . The distance between points and is . Also, there is a sequence that is initially empty. Repeat the following operations from any point until the length of is .

• Let be the number corresponding to the current point. If is not in , add to the end of . Next, move to one of the points whose distance is less than or equal to .

Answer the following queries.

• You are given integers . Let the sequence created by removing elements larger than from be . Among the possible permutations of , answer the number of permutations in which is greater than or equal to and less than or equal to with mod .

represents the -th query.

Each query is given in the following format.

The input satisfies the following constraints.

• All inputs consist of integers.

Output lines. On the -th line, output the answer of the -th query.

样例输入 1

2 4
4 1 1
3 1 3
10 2 7
1 1 1

样例输出 1

4
6
140172
1

样例输入 2

314 6
60522 7560 25373
79445 26896 78962
33447 12441 21469
47202 17227 32455
63982 13450 41311
2156 1226 2148

样例输出 2

925500464
455690352
567782656
893053639
942918900
458845228

In Sample Input 1, There are four possible sequences as in the first query.