LittleElephantAndBoard | Topcoder Archive

Problem Statement

Little Elephant from the Zoo of Lviv has a board with 2 rows and M columns. Each cell of the board must be painted in one of three colors: red, green, or blue.

The board is called magical if and only if it has the following properties:

No two adjacent cells share the same color. (Two cells are adjacent if they share an edge.)
Every 2x2 block contains at least one cell of each of the three colors.

You are given four ints M, R, G and B. Let X be the total number of different magical boards with 2 rows and M columns that contain exactly R red cells, G green cells, and B blue cells. Return the value (X modulo 1,000,000,007).

Definition

Class:: LittleElephantAndBoard
Method:: getNumber
Parameters:: int, int, int, int
Returns:: int
Method signature:: int getNumber(int M, int R, int G, int B)
(be sure your method is public)

Constraints

M will be between 2 and 1,000,000, inclusive.
R, G and B will each be between 0 and 1,000,000, inclusive.
R+G+B will be equal to 2M.

Examples

```
2
```
```
2
```
```
1
```
```
1
```
```
Returns: 4
```
The following 4 different magical boards are possible in this case:
```
2
```
```
2
```
```
2
```
```
0
```
```
Returns: 0
```
No magical board is possible in this case.
```
10
```
```
7
```
```
7
```
```
6
```
```
Returns: 496
```
```
474
```
```
250
```
```
300
```
```
398
```
```
Returns: 969878317
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.