Sau khi p2o2HuaGiaBao đi xem phim chiếu rạp nhân dịp \(30/4\), anh ta nhớ mãi đến cái tháp ô vuông được đặt trước cửa rạp chiếu phim. Ngoài ra, anh ta đã nhận thấy như sau: Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1, 3, 5, 7,...\). Một tháp ô vuông có \(n\) hàng gọi là tháp ô vuông bậc \(n\) (\(n \in \mathbb{N}^*\)). Ví dụ ở hình vẽ trên ta có một tháp ô vuông bậc \(3\).

Yêu cầu: Cho trước một tháp ô vuông bậc \(n\). Hãy đếm xem trong tháp ô vuông này có tất cả bao nhiêu hình vuông tạo thành từ các ô vuông đó.

Input:

• Gồm một số tự nhiên \(n\) (\(1\le n \le 10^{7}\)).

Output:

• Ghi số tự nhiên \(m\) là số lượng hình vuông đã đếm theo yêu cầu. Vì kết quả có thể rất lớn nên cần chú ý chia lấy dưa cho \(10^9+7\).

Example

3

11

Scoring

• Subtask 1 (\(50\)% points): \(1 \le n \le 10^3\)
• Subtask 2 (\(50\)% points): Không có ràng buộc gì thêm