SP15250 SWAP_HRD - Swap (Hard - Level 1000)

Let's play with sequence of non negative integer. Given two sequence of **n** non negative integers (a $ _{1} $ ,a $ _{2} $ ,...,a $ _{n} $ ) and (b $ _{1} $ ,b $ _{2} $ ,...,b $ _{n} $ ). Both sequence has maximum element less than **k**, max(a $ _{1} $ $ _{,} $ a $ _{2} $ ,...,a $ _{n} $ )

First line there is an integer **T** denoting number of test case, then **T** test cases follow. For each case, there are two integers **n** and **k** writen in one line, separated by a space.

For each case, output number of different pair of initial sequence (**a**,**b**), since the answer can be large, output the answer modulo 10 $ ^{9} $ +7.