没有学过组合数学的jwp想自学一下，他随便拿出了一道题：有一个坐标网格，有一只青蛙，开始在 点，它每次可以向右或者向上跳一步，问它跳到 点有多少种方案。由于方案可能很大很大，jwp决定只求方案数对 取模之后的模数（注意 不一定是质数）。然而他发现，这个问题他还不会做，为了不打消他学习组合数学的积极性，zzy决定请你来帮他解决这个问题。
第一行一个整数 ，表示数据组数。
接下来 行，每行三个整数 。
输出 行，每行一个整数表示答案。
1 2 3 100000
10