题目背景

小 L 通过泥萌的帮助，成功解决了牛栏的修建问题。奶牛们觉得主人非常厉害，于是再也不敢偷懒，母牛们奋力挤奶，生娃。子子孙孙无穷匮也！小 L 于是成为了一代富豪！

但是一直困扰小 L 的就是单身问题！小 L 经过长久的寻觅，小 L 终于找到了一个心仪的漂亮妹子。于是，小 L 打算在 520 那天给妹子一个惊喜！（虽然小 L 很节约，但是对妹子还是很阔绰的！）

题目描述

小 L 决定用 $K$ 种珍珠为妹子做一串举世无双的珍珠垂饰。珍珠垂饰是由珍珠连接而成的，其长度可以认为就是珍珠垂饰上珍珠的个数。小 L 现在腰缠万贯，每种珍珠他都拥有 $N$ 颗。根据将珍珠垂饰打开后珍珠不同的排列顺序可以区别不同种类的项链。现在，小 L 好奇自己可以组成多少种长度为 $1$ 至 $N$ 的不同的珍珠垂饰？当然，为显富有，每串珍珠垂饰都要必须由 $K$ 种珍珠连成。 答案取模 $1234567891$。

这一定难不倒聪明的你吧！如果你能帮小 $L$ 解决这个问题，也许他会把最后的资产分给你 $\frac{1}{4}$ 哦！

输入格式

输入包含多组数据。第一行是一个整数 $T$，表示测试数据的个数。每组数据占一行，包含两个整数 $N$ 和 $K$，用一个空格隔开。

输出格式

每组数据输出仅一行，包含一个整数，表示项链的种类数。

2
2 1
3 2

2
8

提示

对于 $40\%$ 的数据，满足 $1\leq N\leq 10^5$,  $0\leq K\leq 30$。

对于 $100\%$ 的数据，满足 $T \leq 10$，$1\leq N\leq 10^9$，$0\leq K\leq 30$。

对于 $70\%\sim100\%$ 的数据，时限 $10$ ms。