Time Limit: 1000 MS  Memory Limit: 6 M


Description

  Sidney想去Gandtom家玩。但Sidney家和Gandtom家之间是高低不平、坑坑洼洼的土路。所以他需要用他的背包装几袋稀的泥,在路上铺平一些干的土,使路变成平整的泥土,才能到Gandtom家见到Gandtom。
  已知现在有种稀的泥,第种稀的泥的体积为,数量为。Sidney的包需要装体积恰好为的稀的泥。
  试求Sidney有多少种携带方案。(如果两种携带方案存在某种稀的泥的携带数量不同,我们认为这两种方案是不同的。)

Input

第一行有一个整数,表示组数。
每组数据第一行有两个正整数
每组数据第二行有个正整数,第个数为

Output

每组样例第一行输出一个整数。表示携带方案数除以1000000007的余数。

Sample Input

1
2 5
3 4

Sample Output

3

Note

这三组方案分别为(1, 4), (2, 3), (3, 2)。