There are only three phases in Swaps life: Sleep, Play and Study. Also, there are two types of emotions Swaps experiences: Happy and Sad. Each phase of his life brings either kind of emotions.

The sleep and the play phase makes Swaps happy whereas the study phase makes him sad. Quite obvious, isn't it? But we know that life isn't that great, one cannot be happy all the time.

Swaps, being a very sensitive guy, doesn't like to mix his emotions in a particular day. So each day, he is in exactly one of the three phases.

Given N which denotes the number of days and K which denotes the exact number of days Swaps needs to be happy out of these N days, can you tell him in how many ways can he achieve this? Since the output value can be very large, take modulo with $1000000007 (10^{9}+7)$.

Input:

The first line of the input contains T, denoting the number of test cases.

The next T lines contain two space-separated integers N and K.

Output:

For each test-case, output a single integer, the number of ways modulo $1000000007 (10^{9}+7)$.

Constraints:

• $1 \le T \le 10^{5}$
• $1 \le N \le 10^{6}$
• $1 \le K \le 10^{6}$
• $K \le N$