Phong ấn Messiah


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Sau 10 năm kể từ ngày Messiah bị chiến đội Go-Busters đánh bại, bọn Vaglass đã một lần nữa hồi sinh cho chủ nhân của chúng.

Lần này Messiah đã được hấp thụ một lượng Enetron khổng lồ, vì vậy hắn không thể bị tiêu diệt như các cách trước đây.

Nhưng do công nghệ của địa cầu đã phát triển sau từng đấy năm, Cục Quản lý Energy đã nắm được cách phong ấn vĩnh viễn Messiah. Đó là sử dụng năng lượng từ các dãy bit có độ dài $N$. Dãy bit này cần bắt đầu bằng bit 1 hoặc kết thúc bởi 2 bit 0.

Hãy giúp Cục và chiến đội Go-Busters biết được số lượng dãy bit họ cần tìm để phong ấn Messiah.

Dữ liệu

  • Một dòng duy nhất chứa số nguyên $N \ (2 \le N \le 10^{18})$.

Kết quả

  • Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.

Ví dụ

Ví dụ 1

input

4

output

10

Comments

There are no comments at the moment.