J. 摆放数量

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

育华学校图书馆在劳动节期间要对图书进行重新摆放。图书馆有一个特殊的书架，书架由 $n$ 层组成（ $1 \leq n \leq 10^{18}$ ）。摆放图书有如下规则：

请你计算第 $n$ 层多少的图书摆放数量。由于方案数可能非常大，你需要将结果对 $10^9 + 7$ 取模。

输入包含两个整数 $n$ ，分别表示书架的层数。

输出一个整数，表示第 $n$ 层图书摆放数量对 $10^9 + 7$ 取模的结果。

子任务编号	数据点占比	$n$ 的范围
1	30%	$1 \leq n \leq 100$
2	30%	$1 \leq n \leq 10^5$
3	40%	$1 \leq n \leq 10^{18}$

劳动节特别赛