Truyền dữ liệu

Trong một sứ mệnh không gian đặc biệt, trung tâm điều khiển trái đất cần thiết lập một giao thức mới để truyền dữ liệu về từ vệ tinh. Dữ liệu được chia thành các gói nhỏ, được biểu diễn bằng một dãy số nguyên không âm \(a(0), a(1), \dots, a(n)\).

Tuy nhiên, hệ thống mã hóa sử dụng một dạng năng lượng đặc biệt, trong đó chi phí để truyền bit \(i\) là \(a(i) \cdot 2^i\) đơn vị năng lượng. Vì vệ tinh chỉ có thể phát tín hiệu trong thời gian ngắn, tổng chi phí truyền phải không vượt quá mức năng lượng cho phép, cụ thể là:

Bạn được yêu cầu xác định có bao nhiêu dãy \((a(0), a(1), \dots, a(n))\) thỏa mãn điều kiện trên. Mỗi \(a(i)\) là một số nguyên không âm.

Input

• Một dòng duy nhất chứa số nguyên \(n\) \((0 \leq n \leq 249)\).

Output

• In ra một số nguyên duy nhất --- số dãy thỏa mãn điều kiện, lấy phần dư theo \(10^9 + 7\).

Example

5

25510

35

490154274

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 25 & \(n \leq 10\)

2 & 75 & Không có ràng buộc bổ sung

\hline
\endtabular