#P16400. Pendant

Pendant

题目背景

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

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

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

题目描述

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

一条吊坠由一个长度为 LL 的珍珠序列构成,其中

1≤L≤N.1\le L\le N.

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

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

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

12345678911234567891

取模。

输入格式

第一行包含一个整数 TT,表示测试用例数量。

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

输出格式

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

样例输入

2
2 1
3 2

样例输出

2
8

样例解释

对于第一组数据,只有一种珍珠,可制作长度为 11 或 22 的吊坠,因此答案为 22。

对于第二组数据:

  • 长度为 11 时,不可能同时使用两种珍珠;
  • 长度为 22 时,有 22 种合法排列;
  • 长度为 33 时,有 66 种合法排列。

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

数据范围

对于所有测试数据:

1≤T≤10,1\le T\le 10, 1≤N≤109,1\le N\le 10^9, 1≤K≤30.1\le K\le 30.