Python Code

You have an infinite number of $4$ types of lego blocks of sizes given as $($depth x height x width$)$:

d h w

$111$

$112$

$113$

$114$

Using these blocks, you want to make a wall of height n and width m$.$ Features of the wall are:

$-$ The wall should not have any holes in it$.$

$-$ The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks.

$-$ The bricks must be laid horizontally.

How many ways can the wall be built?

Example

n$=2$

m$=3$

The height is $2$ and the width is $3.$ Here are some configurations:

These are not all of the valid permutations. There are $9$ valid permutations in all.

Function Description

Complete the legoBlocks function in the editor below.

legoBlocks has the following parameter$($s$)$:

int n: the height of the wall

int m: the width of the wall

Returns

$-$ int: the number of valid wall formations modulo $(10^9+7)$

Input Format

The first line contains the number of test cases t$.$

Each of the next t lines contains two space$-$separated integers n and m$.$

Constraints

$1<=$t$<=100$

$1<=$n$,$ m$<=1000$

Sample Input

STDIN Function

$-------------$

$4$ t $=4$

$22$ n $=2,$ m $=2$

$32$ n $=3,$ m $=2$

$23$ n $=2,$ m $=3$

$44$ n $=4,$ m $=4$

Sample Output

$3$

$7$

$9$

$3375$