問題文


個のスイッチがつながっている電球があります。 スイッチには A または B つの状態があり、自由に切り替えることができます。 電球には OFF または ON の状態があります。

はじめ、スイッチはすべて A で、 電球は OFF です。 任意のスイッチを つ切り替えると、電球の状態が切り替わります。

電球が ON になるような状態の組み合わせが何通りあるか求めてください。 なお、答えは非常に大きくなる可能性があるので、 で割ったあまりを出力してください。

制約


  • 入力は整数

入力


N

出力


答えを 行に出力してください。

入出力例


入力例1
1
出力例1
1

つのスイッチがあり、 B のときのみ電球は ON になります。

入力例2
3
出力例2
4

電球が ON になる組み合わせは AAB, ABA, BAA, BBB です。

入力例3
100
出力例3
988185646

で割ったあまりを出力してください。

提出


Go (1.14)