TOKI1493 - Swap (Original)

NyanCoder have a new hobby, that hobby is playing with string and He love sorted string. NyanCoder want to make two strings a and b, both string have equal length N. At that both string, NyanCoder want to swap some element (or none) on string a with element on string b that located at same position. More specifically, NyanCoder may choose integer i, and then swap a[i] with b[i].

NyanCoder want when he finished playing, both new string have non-decreasing element (e.g. "aabbb", "cccdee" but not "bbaa" or "ebd"). Help NyanCoder to count number of possible initial string a and b with length N that meet the condition that NyanCoder want.

Input

First line there is an integer T denoting number of test cases, then T test cases follow.
For each test case, there is two integers N and M, separated by a space where N denoting length of both string, and alphabet that can be used on that both string is M first letters (lower case) on latin alphabet ('a','b','c', and so on). For example, if M=3, all character on both string is formed with only first 3 lower case letters ('a','b', and 'c').

Output

For each test case, output an integer which is the number of possible initial string a and b with length N and meet all condition that have described before. Since that answer can be too large, take modulo 109+7

Example

Input:
1
2 2

Output:
11

Explanation

When N=2 and M=2, all pair of initial sring that meet the condition is:

  1. "aa", "aa"
  2. "aa", "ab"
  3. "aa", "bb"
  4. "ab", "aa"
  5. "ab", "ab"
  6. "ab", "bb"
  7. "bb", "aa"
  8. "bb", "ab"
  9. "bb", "bb"
  10. "ba", "ab"
  11. "ab", "ba"

Subtask

  • Subtask 1 (10 points): 1<=N<=5, 1<=M<=26
  • Subtask 2 (20 points): 1<=N<=10, 1<=M<=26
  • Subtask 3 (30 points): 1<=N<=40, 1<=M<=26
  • Subtask 4 (40 points): 1<=N<=1000, 1<=M<=26

To get AC on this problem you need to solve at least one test data (min possible points on rank table for this problem is 10).

Other Info

This is a copy of TOKI problem, with some small changes to become suitable with SPOJ server and judge:

  • Language, because SPOJ is International Online Judge, so I must translate the problem statement and other to English before publishing it.
  • I/O format, because SPOJ server is busy (too many submission per minute), to make it stable then I should make number of input data as small as possible, so my solution is to put multiple test case in one file.
  • Test Case, because I don't know official test case used on this problem, I build my own test case. All possible case that meet the constraints will appear once on each test data.

Problem setter who created this problem is Risan Petrus. I only copy his problem that used on TOKI open contest june 2013 to SPOJ because for me this problem is very interesting. I like it, and I want every user on SPOJ can enjoy his problem too.

 


See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-06-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TOKI Open Contest, June 2013, Problem 03

hide comments
2014-06-03 20:32:05 (Tjandra Satria Gunawan)(曾毅昆)
Info: Because of copyright problem, now all your submission to this problem will be visible to Risan Petrus too, and he has full access for editing this problem (or removing this problem from Main problemset). But only me have full access for all other version of this problem. This means that only me and submission owner (you) can view your submission to Swap (Easy), Swap (Medium), and Swap (Hard) problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.