問題文


以上 以下の正整数全体の集合 があります. の部分集合 であって,以下の条件を満たすものが何通りあるか求めてください.

  • 任意の正整数 について

ただし答えは非常に大きくなる可能性があるので, で割った余りを出力してください.

制約


  • は整数である

入力


入力は以下の形式で標準入力から与えられる.

出力


答えを出力せよ.

サンプル


入力例1
2
出力例1
3

が条件を満たします.

入力例2
3
出力例2
5

が条件を満たします.

入力例3
2022
出力例3
124881012

Submit


Go (1.14)