Cho số nguyên \(n\). Đếm số lượng lưới \(n×n\) khác nhau, trong đó mỗi ô có thể là đen hoặc trắng. Hai lưới được coi là khác nhau nếu không thể quay một trong số chúng để trông giống nhau.

Input

• Dòng đầu tiên chứa một số nguyên \(n (1≤n≤10^9 ).\)

Output

• In ra một số nguyên: số lượng lưới theo modulo \(10^9+7 \)

Ràng buộc

• Subtask 1: 75% test với \(n≤10^6.\)

• Subtask 2: 25% test với \(n≤10^9\)

Sample Input

4

Sample Output

16456