問題文


以上の整数 に対し、関数 を次のように定義します。

  • のとき
  • のとき

整数 が与えられるので、 で割った余りを求めてください。

制約



は整数

入力


出力


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

入力例1


2

出力例1


4

入力例2


100

出力例2


976371285

Submit


Go (1.14)