Once upon a time in the quaint village of Turlington, there lived a talented artisan named Ella. Ella had a unique skill – she could transform any floor into a mesmerizing mosaic using special tiles. These magical tiles were of size \(1\times X\), and Ella's artistic flair knew no bounds.

One day, the villagers gathered around Ella's workshop, curious about the secrets behind her enchanting tile arrangements. Ella, always happy to share her knowledge, decided to turn this curiosity into a challenge. She introduced the villagers to a puzzle: The problem of finding the absolute difference between the number of \(distinct\) ways and the number of \(distinct\ ordered\) ways to tile a floor of size \(N \times X\) . The twist in the tale was that the tiles could be rotated in any direction, meaning a \(1 \times X\) tile could also become an \(X \times 1\) tile.

The villagers, eager to test their problem-solving skills, embarked on a series of \(Q\) queries. In each query, they provided two numbers, \(N\) and \(X\), representing the dimensions of the floor and the magical tiles, respectively. Ella emphasized that the answers should be calculated modulo \(10^9 + 7\) since the answer can be very large.

Distinct Ways:

• Definition: "Distinct ways" refer to the count of unique ordered arrangements or permutations of tiles on the floor, considering both the orientation and the order of the tiles.
• Example: Suppose \(N = 4\) and \(X = 2\). The distinct ways will be \([1 \times X, 1 \times X, 1 \times X, 1 \times X], [1 \times X, 1 \times X, X \times X], [1 \times X, X \times X, X \times 1], [X \times X, 1 \times X, 1 \times X], [X \times X, X \times X]\).

Distinct Ordered Ways:

• Definition: "Distinct ordered ways" refer to the count of unique arrangements or combinations of tiles on the floor, considering the orientation of the tiles but not the order.
• Example: Suppose \(N = 4\) and \(X = 2\). The distinct ordered ways will be \([1 \times X, 1 \times X, 1 \times X, 1 \times X], [1 \times X, 1 \times X, X \times X], [X \times X, X \times X]\). In ordered ways, the set of tiles arrangements will be added but not the order of the tiles.

Input format

• The first line contains an integer \(Q\) representing the number of queries.
• For each of the \(Q\) queries, there are two space-separated integers \(N\) and \(X\).

Output format

• For each query, output a single integer representing the absolute difference between the number of distinct ways and the number of distinct ordered ways to tile the floor, considering the ability to rotate the tiles.
• Since the answer can be very large, output the result modulo \(10^9 + 7\).

Constraints