A22536.珍珠项链

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

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

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

40 % ：1<= N<= 100000,  0<= K<= 30

100% ：T <= 10， 1<= N<= 1000000000,  0<= K<= 30

70%-100%：时限10ms