Innocent Swaps and His Emotions
Tag(s):

## Combinatorics, Easy-Medium, Math, Modular exponentiation, approved

Problem
Editorial
Analytics

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$
SAMPLE INPUT
3
1 1
2 1
3 2

SAMPLE OUTPUT
2
4
12

Explanation

In the first test case, he needs to be happy on Day 1. Hence, answer is 2 (He can either play or sleep).

In the second test case, he can be happy either on Day 1 or Day 2. So number of ways = 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...