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

SAMPLE INPUT
2
1 1
2 10

SAMPLE OUTPUT
26
52

Explanation

Test Case #1:

All single character strings constitute the list of incredible strings.

Test Case #2:

All single character and two characters strings are incredible strings.

见题面

见题面