给定 组正整数 ，对下面的式子求值：
其中 表示组合数 。
由于答案可能很大，你只需要输出答案对 取模的结果。
第一行输入两个正整数 ，分别表示 的上界以及测试组数。
第 至 行每行输入三个正整数 含义见题目描述。
输出 行，每行输出一个询问的答案。
样例输入
5 3 2 2 3 4 5 5 3 4 5
样例输出
24 160 880
对于所有测试数据，保证 。
输入输出规模较大，请选手使用较快的输入输出方式。