404399: GYM101498 D Counting Paths

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Consider an infinite binary tree with each node has exactly two children, and two given integers a and b, count the number of paths in the infinite binary tree that satisfy the following rules:

• The path starts from the root of the tree.
• The length of the path is equal to a (The length of a path is the total number of edges from the root to the final node on that path).
• The number of change of direction along the path is equal to b. Change of direction means, going to your right child if you are the left child of your parent or vise versa.

As the number of paths can be too large, print it (modulo 10⁹ + 7).

The first line of the input contains an integer T (1 ≤ T ≤ 10⁵), where T is the number of the test cases.

Each test case has one line that contains two integers a and b (0 ≤ b < a ≤ 10⁵), the length of the path and the number of change of direction along it.

For each test case, print a single integer that represents the number of paths that satisfy the mentioned rules (modulo 10⁹ + 7).

2
2 1
4 3

2
2