You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width): dhw111112113114 Using these blocks, you want to make a wall of height and width . 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 The height is and the width is . Here are some configurations: These are not all of the valid permutations. There are 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 Input Format The first line contains the number of test cases . Each of the next lines contains two space-separated integers and . Constraints Sample Input STDIN Function ----- -------- 4 t = 4 2 2 n = 2, m = 2 3 2 n = 3, m = 2 2 3 n = 2, m = 3 4 4 n = 4, m = 4 Sample Output 3 7 9 3375 Explanation For the first case, we can have: For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is and
You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):
Using these blocks, you want to make a wall of height and width . 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
The height is and the width is . Here are some configurations:
These are not all of the valid permutations. There are 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
Input Format
The first line contains the number of test cases .
Each of the next lines contains two space-separated integers and .
Constraints
Sample Input
Sample Output
Explanation
For the first case, we can have:
For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is and .
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
