問題
https://hoj.hamako-ths.ed.jp/onlinejudge/problems/521
ほものくんはこの問題の N がもっと大きい場合について何通りの剣剣派が放てるかを求めてほしいと言ってきました．
ほものくんの代わりに何通りの剣剣派が放てるかを求めてあげてください．
ただし，答えは非常に大きくなる可能性があるので 109 +7 で割った余りを出力してください．
入力
N
- 1 行に長さ N が与えられる。
制約
- 1 ≦ N ≦ 1018
出力
- 1 行に 109 +7 で割った余りを出力する．改行を忘れないこと．
入出力例
入力例1
1000000
出力1
210671794
- うん
入力例2
1000000000
出力2
1
- オッ
入力例3
1000000000000000000
出力3
23833
- アアッ