Tetrahedron

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Một con kiến bắt đầu ở đỉnh $D$ của tứ diện. Mỗi bước nó đi theo một cạnh sang một trong ba đỉnh khác. Hãy đếm số cách sau đúng $n$ bước quay lại $D$.

Input

Dòng duy nhất chứa $n$.

Output

In số cách modulo $10^9+7$.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

2

Output

3

Explanation

The output follows directly from the rules above.