配点: 1000 点
問題文
正整数 N ,所以4^0 + 4^1 + \dots + 4^N 该值应乘以 1\,000\,000\,007 后的余数。
制約
- 1 \leq N \leq 10^{18}
- N 是一个整数
入力
输入是按以下格式从标准输入给出的。
N
出力
4^0 + 4^1 + \dots + 4^N 该值应乘以 1\,000\,000\,007 后的余数。
入力例 1
3
出力例 1
85
4^0 + 4^1 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85 所以, 您最多只能移动到85 。
入力例 2
45
出力例 2
414031736
4^0 + 4^1 + \dots + 4^{45} = 1650586719047173699865498965 所以, 您最多只能移动到1650586719047173699865498965 该值应乘以 1\,000\,000\,007 时的余数 查找 414031736 。