Nhiệm vụ của bạn là đếm số lượng lưới ô vuông \(n \times n\) khác nhau mà mỗi ô vuông có màu đen hoặc trắng.

Hai lưới được coi là khác nhau nếu không thể xoay một trong số chúng để chúng trông giống nhau.

Input

• Một dòng duy nhất là một số nguyên \(n\): kích thước của lưới.

Output

• In ra một số nguyên: số lượng lưới chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq n \leq 10 ^ 9\)

Example

Sample input

4

Sample output

16456