题目描述

猪灵是一种生活在下界的生物。每当它们战胜疣猪兽的时候,猪灵们就会围成一圈,摇动双耳开始跳胜利之舞。

由于猪灵们刚刚结束一场战斗,因此它们的脾气变得相当暴躁,在跳胜利之舞的过程中,每只猪灵都有$\frac{1}{2}$的概率被激怒。当有两只相邻的猪灵都被激怒时,气氛就变得微妙了起来,它们会开始互相攻击,从而导致整场胜利之舞的失败。

由于猪灵的数量实在太多了,因此想请你帮忙计算一下它们成功跳完胜利之舞的概率。

假设结果为$\frac{p}{q}$,你应该输出$p\times q^{-1} \mod (10^9+7)$


输入格式

一个整数n表示猪灵的数量。 ($3 \le n \le 10^{10^6}$)


输出格式

对于每组数据输出一个整数表示答案,独占一行。


样例数据

输入

4

输出

937500007

备注

当n=4时,如下7种情况下猪灵可以成功跳完胜利之舞,概率为$\frac{7}{16}$。
(红色圆圈表示被激怒的猪灵)


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务