P2768 Pearl Necklace

With everyone’s help, Xiao L successfully solved the cowshed construction problem. The cows think their owner is amazing, so they no longer dare to slack off. The cows work hard to produce milk and have calves. Generations continue endlessly! Xiao L has thus become a wealthy man! However, what still troubles Xiao L is being single! After a long search, he finally found a lovely girl he likes. So, he plans to give her a surprise on 520! (Although Xiao L is frugal, he is still generous to the girl!)

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!

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.

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

- 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