Cho một tứ diện, đánh dấu các đỉnh lần lượt là \(A, B, C, D\).

Một con kiến ​​đang đứng trên đỉnh \(D\) của tứ diện. Con kiến ​​khá tích cực di chuyển và nó không chịu nhàn rỗi. Với mỗi bước đi, nó bước từ một đỉnh tới đỉnh khác dọc theo một số cạnh của tứ diện. Con kiến ​​không bao giờ chịu đứng yên ở một chỗ.

Yêu cầu: Đếm số cách mà con kiến ​​có thể đi từ đỉnh \(D\) ban đầu rồi quay về chính nó trong đúng \(n\) bước. Nói cách khác, bạn sẽ được yêu cầu tìm ra số con đường tuần hoàn khác nhau có chiều dài \(n\) từ đỉnh \(D\) đến chính nó. Vì số có thể khá lớn nên bạn nên in theo \(modulo (10^9 + 7)\).

Input

• Dòng đầu tiên chứa số nguyên duy nhất \(n (1 \le n \le 10^7)\) - chiều dài của đường đi.

Output

• In số nguyên duy nhất là kết quả tìm được \(modulo (10^9+ 7)\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^7\)
• Subtask \(3\) (\(50\%\) số điểm): \(n \le 10^{14}\)

Example

2

3