红色珠子

Time Limit: 4000 ms

Memory Limit: 65536 KB

Description

fishhead有一串珠子,当然是环状的,而且均匀分布在圆环上。现在fishhead有红、黄、蓝三种颜色,想要给这串珠子涂色,使得珠子变得好看一点,每个珠子都必须涂上其中的一种颜色,并且只能涂一种颜色,不能一个珠子涂多种,这样不符合fishhead的省美观,于是fishhead就好奇,一共有多少种本质上不同的涂法呢?如果一种涂法的珠子通过旋转和翻转能够变成另外一种涂法,那么这两种涂法本质上是相同的。
聪明的鱼儿子一下就解决了这个问题,fishhead很高兴,不过紧接着就是烦恼,因为鱼儿子给fishhead出了一个更难的题目,鱼儿子喜欢红色,现在要求,涂好颜色后的这么多珠子中必须有一定数量的红色,他想知道在这个限制条件下一共有多少种本质上不同的涂法?因为这个数字可能很大,所以只要知道这个数字Mod 1000000007的值。

Input

数据的第一行输入一个T(T<=50),表示有T组测试数据。 接下来每组测试数据包括1行,2个数字,n和m(1<=n<=100000, 0<=m<=n),表示有n个珠子,最后至少有m个红色的珠子。

Output

每组测试数据输出一行一个数字。

Sample Input

2
3 0
3 2

Sample Output

10
3

Hint

Source

“掌赢杯”南京理工大学第六届程序设计大赛

提交代码