牛牛进入了方格世界，方格世界由个方格构成的高为宽为的矩形，牛牛所在的方格为，而方格世界的出口在。在方格世界中，牛牛只能向上走或者向左或向右走，而且牛牛走过的方格不能再次进入。牛牛想知道他有多少种走出方格世界的路径，答案可能很大请对取模。

输入描述:

第一行为一个，表示有组数据。接下来有行，每行有两个数字和。

输出描述:

输出为行，每行一个数字表示答案。