SKIT's Language Department are studying an incredible string which is actually a palindrome. The students are trying to build all possible incredible strings that contains 1 to K lowercase characters.

Their is a constraint to the string which makes it incredible that each string can contain at most M distinct characters.

Your task is to help those students by finding out the total number of possible incredible strings.

Note: Answer could be very large, hence print answer modulo 1234567891.

Input:

First line of input contains an integer T denoting the number of test cases. Each test case contains two space separated integers K and M.

Output:

Print the total number of possible strings.

Constraints:

• 1 <= T <= 25
• 1 <= K <= 10^9
• 1 <= M <= 26