1586: 火星货币

　　传说中，火星上发行火星币（地球上怎么不发行地球币呢？！），而且每年都会发行不同面额的火星币，面额都是 k 的自然数幂次，即1，k，k²……（直到无穷大，只要你有这么多钱。）其中的底数 k 并非定值，会根据火星王的喜好每年一换。
　　每年年初发货币时，火星上就会举行一场 ACM（Arithmetic Contest in Mars）大赛，其主要内容就是计算 p 火星币若由当年新发行的不同面额的货币组合而成，有多少种不同的组合方法。
　　为了保证你在重返火星时能够在 ACM 大赛中脱颖而出，你打算现在就写一个程序，根据不同的 k 和 p，计算出如果火星王把面额的底数定为 k，那 p 火星币有多少种不同的组合方法。

　　第一行，一个整数 n，表示以下一共有 n (n≤50) 组数据。 　　以下 n 行，每行两个整数 k (1<k<50) 和 p (1≤p<1000000)，中间用一个空格隔开。

　　n 行，每行一个整数，对应的 k 和 p 一共有多少种组合方式。由于最终结果可能会非常大，你只需要输出计算结果对 20080607 的余数。

1
2 7

6

用1, 2, 4...组成 7 有 6 种方法：(1,1,1,1,1,1,1),(1,1,1,1,1,2),(1,1,1,2,2),(1,2,2,2),(1,1,1,4),(1,2,4)。