Daylight君は日間の朝食の献立表を作ることにしました。献立表には、日それぞれについて、その日に食べる朝食のメニューを記載します。 朝食のメニューは以下の種類のパンから種類が選ばれます。
Daylight君は同じ味のパンを連続で食べると飽きてしまいます。そこで、献立には以下の制約を設けることにしました。
日それぞれについて、種類のパンから種類を選んで作られた献立表は通り存在しますが、このうち上記の制約を満たす献立表が何通り存在するか、で割った余りを出力してください。
入力はすべて整数です。
N
問題文中の制約を満たす献立表が何通り存在するか、で割った余りを出力してください。
2
9
制約を満たす献立として以下のように通りが存在します。
3
20