Description

Xiao L decides to make a unique pearl necklace using $K$ kinds of pearls. A pearl necklace is a sequence of pearls, and its length is the number of pearls in the sequence. Now he is very rich and owns $N$ pearls of each kind. Two necklaces are considered different if, when laid out straight, their pearls are in different linear orders. Xiao L wonders how many different necklaces of lengths from $1$ to $N$ he can make. To show wealth, each necklace must use all $K$ kinds of pearls. Output the answer modulo $1234567891$.

This should be easy for you! If you can help Xiao L solve this problem, he might give you $1/4$ of his assets!

Input Format

The input contains multiple testdata. The first line is an integer $T$, which is the number of testdata. Each testdata occupies one line and contains two integers $N$ and $K$, separated by a space.

Output Format

For each testdata, output exactly one line containing one integer, which is the number of kinds of necklaces.

2
2 1
3 2

2
8

Hint

• 40%: $1 \le N \le 100000$, $0 \le K \le 30$.
• 100%: $T \le 10$, $1 \le N \le 10^9$, $0 \le K \le 30$.
• 70%–100%: time limit $10$ ms.

Translated by ChatGPT 5