CF166E.Tetrahedron

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given a tetrahedron. Let's mark its vertices with letters $A$ , $B$ , $C$ and $D$ correspondingly.

An ant is standing in the vertex $D$ of the tetrahedron. The ant is quite active and he wouldn't stay idle. At each moment of time he makes a step from one vertex to another one along some edge of the tetrahedron. The ant just can't stand on one place.

You do not have to do much to solve the problem: your task is to count the number of ways in which the ant can go from the initial vertex $D$ to itself in exactly $n$ steps. In other words, you are asked to find out the number of different cyclic paths with the length of $n$ from vertex $D$ to itself. As the number can be quite large, you should print it modulo $1000000007$ ( $10^{9}+7$ ).

输入格式

The first line contains the only integer $n$ ( $1<=n<=10^{7}$ ) — the required length of the cyclic path.

输出格式

Print the only integer — the required number of ways modulo $1000000007$ ( $10^{9}+7$ ).

输入输出样例

输入#1
```
2
```
输出#1
```
3
```
输入#2
```
4
```
输出#2
```
21
```

说明/提示

The required paths in the first sample are:

$D-A-D$
$D-B-D$
$D-C-D$

首页