問題文
以上 以下の正整数全体の集合 があります． の部分集合 であって，以下の条件を満たすものが何通りあるか求めてください．
- 任意の正整数 について
ただし答えは非常に大きくなる可能性があるので， で割った余りを出力してください．
制約
- は整数である
入力
入力は以下の形式で標準入力から与えられる．
出力
答えを出力せよ．
サンプル
入力例1
2
出力例1
3
が条件を満たします．
入力例2
3
出力例2
5
が条件を満たします．
入力例3
2022
出力例3
124881012
提出
登録なしで提出できます。
Go (1.14)