题目背景

情人节到了，Alex 想为女朋友制作一条特别的珍珠吊坠。

Alex 拥有 $K$ 种不同种类的珍珠，并且每一种珍珠都有足够多的数量。吊坠可以看作一串按顺序排列的珍珠；珍珠的排列顺序不同，制作出的吊坠也被认为不同。

为了让吊坠足够丰富，Alex 要求每一种珍珠都必须至少使用一次。

题目描述

给定两个正整数 $N,K$。

一条吊坠由一个长度为 $L$ 的珍珠序列构成，其中

序列中的每颗珍珠均属于 $K$ 种珍珠之一，并且这 $K$ 种珍珠都必须在序列中至少出现一次。

两个吊坠不同，当且仅当它们的长度不同，或者存在某个位置上的珍珠种类不同。

请计算一共可以制作多少种不同的吊坠。答案对

取模。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行包含两个整数 $N,K$，表示吊坠长度不超过 $N$，珍珠一共有 $K$ 种。

输出格式

对于每组测试用例，输出一行一个整数，表示不同吊坠的数量对 $1234567891$ 取模后的结果。

样例输入

2
2 1
3 2

样例输出

2
8

样例解释

对于第一组数据，只有一种珍珠，可制作长度为 $1$ 或 $2$ 的吊坠，因此答案为 $2$。

对于第二组数据：

• 长度为 $1$ 时，不可能同时使用两种珍珠；
• 长度为 $2$ 时，有 $2$ 种合法排列；
• 长度为 $3$ 时，有 $6$ 种合法排列。

所以答案为 $2+6=8$。

数据范围

对于所有测试数据：