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
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
1000000
500000
1000000
500000
Returns: 4
1882
1309
1329
1126
Returns: 429528779
1636
1005
1089
1178
Returns: 458100092
1407
870
879
1065
Returns: 565988207
1652
1150
1027
1127
Returns: 665947468
1913
1356
1352
1118
Returns: 386723792
1902
1235
1335
1234
Returns: 863351662
1690
1274
1032
1074
Returns: 974882688
14029
9564
9838
8656
Returns: 149001955
14646
9583
10370
9339
Returns: 756977050
10814
7090
7021
7517
Returns: 262165683
13474
8920
8574
9454
Returns: 824992682
19557
13205
12824
13085
Returns: 637415705
11971
8529
7141
8272
Returns: 127529245
13439
9525
9230
8123
Returns: 238656502
16663
11649
11812
9865
Returns: 847263967
15248
9665
9774
11057
Returns: 263986863
15428
11092
9862
9902
Returns: 793849693
10066
5617
6897
7618
Returns: 767413806
196840
131728
129524
132428
Returns: 198903284
193520
126027
129342
131671
Returns: 716066657
117363
74376
80553
79797
Returns: 744216056
106352
71784
69315
71605
Returns: 746213859
186123
125479
126751
120016
Returns: 303025003
143845
96844
97315
93531
Returns: 828191817
138011
91619
90339
94064
Returns: 646125388
872126
584442
584853
574957
Returns: 658304771
974604
646119
654151
648938
Returns: 327270374
857314
567553
574081
572994
Returns: 150008901
586599
388970
392362
391866
Returns: 371023790
677873
453724
446179
455843
Returns: 967021043
848278
566768
562578
567210
Returns: 813605793
574422
383601
382721
382522
Returns: 690043559
2
2
2
0
Returns: 0
2
0
2
2
Returns: 0
2
3
1
0
Returns: 0
2
0
1
3
Returns: 0
3
0
3
3
Returns: 0
2
4
0
0
Returns: 0
2
0
4
0
Returns: 0
2
0
0
4
Returns: 0
1000000
666666
666667
666667
Returns: 409107937
999998
500000
600000
899996
Returns: 66098697
1000000
700000
700000
600000
Returns: 404998516