SP28180 GOC11B - Mr.BG Hates Palindrome

BG先生是个很忙的人。所以你有足够的时间（1000毫秒）来帮助他。 现在，他有一袋弹珠，上面写着不同的字母。把这些弹珠放在一排的 N 个盒子里。恰好有 M 种不同类型的弹珠，每种类型有 N 种。 现在，他只将 N 个弹珠（M*N 中）一个一个地放入 N 个盒子中，完成后，他将弹珠上的字母写在纸上，形成一个字符串。由于BG先生讨厌回文字符串（从两边读取相同的字符串，例如 MADAM），他一找到回文字符串就将其从纸上擦除。 现在他想知道如果他可以尝试所有可能的组合将弹珠放入盒子中，他可能会在纸上得到多少不同的字符串。可能有**很多**字符串，所以其输出答案 **%1000000007**

输入以整数 TC (

对于每个案例，输出写在纸上的案例编号和字符串总数（%1000000007）。