カラーで塗ろう

あなたは、ストライプを3色（red、blue、orange）で塗りたいと考えています。ストライプは1ユニットごとに1色を使って塗りますが、より目立つように次のルールを設けました:

1. 同じ色を隣り合わせに配置してはいけません。

2. blueは必ずredとorange、あるいはorangeとredの間に配置します。

ストライプ全体がnユニットあるとき、作成できる異なるパターンは何通りになるでしょうか?

入力

入力には単一の整数n (1 ≤ n ≤ ) が与えられます。

出力

作成できるストライプの総数を出力してください。結果が非常に大きくなる可能性があるため、で割った余りを出力してください。

例

解説

1. (red) (orange)

2. (red, orange) (orange, red)

3. (orange, red, orange) (red, blue, orange) (orange, blue, red) (red, orange, red)