atcoder#ABC279G. [ABC279G] At Most 2 Colors
[ABC279G] At Most 2 Colors
Score : points
Problem Statement
There is a grid with squares, numbered from left to right.
Takahashi prepared paints of colors and painted each square in one of the colors. Then, there were at most two colors in any consecutive squares. Formally, for every integer such that , there were at most two colors in squares .
In how many ways could Takahashi paint the squares? Since this number can be enormous, find it modulo .
Constraints
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer as an integer.
3 3 3
21
In this input, we have a grid. Among the ways to paint the squares, there are ways to paint all squares in different colors, and the remaining ways are such that there are at most two colors in any consecutive three squares.
10 5 2
1024
Since , no matter how the squares are painted, there are at most two colors in any consecutive squares.
998 244 353
952364159
Print the number modulo .