← 返回题目列表

AtCoder · math_and_algorithm_as

053. 4^N 之和

中文机器翻译题面 查看原题

配点: 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 。