小蓝要为一门课程安排助教值班表。值班表持续 天，共有 名助教，编号为 到 。
每一天可以安排若干名助教值班。整份值班表需要满足以下要求：
一份值班表的总工作量定义为所有助教的值班天数之和。也就是说，若第 名助教一共值班 天，则总工作量为：
现在要求总工作量恰好为 。请你计算有多少种值班表满足要求。由于答案可能很大，你只需要输出答案对 取模后的结果即可。
第一行包含一个正整数 ，表示询问组数。
接下来 行，每行包含三个整数 ，分别表示值班表持续的天数、助教人数以及要求的总工作量。
输出 行，每行包含一个整数，表示对应询问的答案。
4 4 2 4 5 2 6 6 1 4 7 2 8
9 8 3 36
对于第一组询问，。
用 表示一种值班表，其中 是 号助教的值班日期， 是 号助教的值班日期。所有满足要求的值班表为：
因此答案为 。
对于 的评测用例，, , , ;
对于所有评测用例，, , , 。
