カラーで塗ろう
あなたは、ストライプを3色（
red、blue、orange）で塗りたいと考えています。ストライプは1ユニットごとに1色を使って塗りますが、より目立つように次のルールを設けました:- 同じ色を隣り合わせに配置してはいけません。
blueは必ずredとorange、あるいはorangeとredの間に配置します。
ストライプ全体が
nユニットあるとき、作成できる異なるパターンは何通りになるでしょうか?入力
入力には単一の整数
n (1 ≤ n ≤ ) が与えられます。出力
作成できるストライプの総数を出力してください。結果が非常に大きくなる可能性があるため、で割った余りを出力してください。
例
入力 | 出力 |
1 | 2 |
2 | 2 |
3 | 4 |
解説
- (
red) (orange)
- (
red,orange) (orange,red)
- (
orange,red,orange) (red,blue,orange) (orange,blue,red) (red,orange,red)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB