Nhiệm vụ của bạn là đếm số lượng lưới ~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 cái này để thu được cái kia.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~: kích thước của lưới.

Kết quả

In ra một số nguyên: số lượng lưới modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 10^9~

Ví dụ

Dữ liệu vào:

4

Kết quả:

16456