There are \(n\) strings of even length and \(m\) strings of odd length. You can select any number of strings (non-zero) from these collections and the resulting string is the concatenation of the chosen strings. You cannot break any string, therefore, you either select the whole string or you do not select it at all.

The \(total\_length\) of the string is equal to the sum of the length of all the selected strings. Your task is to determine how many of these \(total\_length\) are even. Since this number can be very large, print it modulo \(10^9 + 7\).

Input format

• The first line contains a single integer \(T\) denoting the number of test cases. \((1 \le T \le 10^5)\)
• Next \(T\) lines contain two space-separated integers \(n\) and \(m\) as described in the problem statement. \((1 \le n, m \le 10^6)\)

Output format

Print a single integer denoting the answer to the problem modulo \(10^9 + 7\).