机房有n个小朋友, 而日记有m 本小日记，她想把这些小日记赠给小朋友们。每本 小日记都是与众不同的。 为了避免小朋友们攀比，日记不能同时将小日记赠给两个相邻的小朋友(当然，她 过后会赠其它的东西啦qwq)。 日记如果剩下了小日记没赠出去，会感到很难过，因此她必须将所有小日记赠出 去。 可爱的洛浔想要知道日记有多少种赠送小日记的方案。作为机房最强Oler的你，能 够帮助洛浔和日记解决这个问题吗? 洛浔不喜欢太大的数喵，因此她想让你输出答案对P取模的结果。 两个方案不同，当且仅当存在至少一个小朋友获得的小日记编号不同 (没有获得则 视为获得了小日记0)。 多个平行世界里，这一瞬间的状态是不一样的。因此洛浔想要分别知道T个平行世 界里的答案。(本题采用多组数据)

所有小于10^9.