Một trung tâm dữ liệu đang vận hành \(n\) cụm máy chủ để xử lý tính toán hiệu năng cao. Nhằm tối ưu hóa năng lực tính toán, hệ thống được thiết kế theo kiến trúc phân tầng vô cùng đặc biệt. Cụ thể, tại cụm máy chủ thứ \(i\) (\(1 \le i \le n\)), kiến trúc được tổ chức chặt chẽ thành ba tầng như sau:

• Tầng 1: Vận hành đúng \(i\) máy chủ điều phối trung tâm.
• Tầng 2: Mỗi máy chủ điều phối chịu trách nhiệm quản lý trực tiếp \(i\) máy trạm.
• Tầng 3: Mỗi máy trạm được cấp phát đúng \(i\) luồng xử lý độc lập để thực thi tác vụ.

Yêu cầu: Cho biết số lượng cụm máy chủ \(n\). Hãy tính tổng số lượng luồng xử lý độc lập được thiết lập trong toàn bộ trung tâm dữ liệu (gồm cả \(n\) cụm). Vì kết quả có thể rất lớn, chỉ cần in ra phần dư của tổng này khi chia cho \(10^9 + 7\).

Input

• Dòng duy nhất gồm một số nguyên dương \(n\).

Output

• Dòng duy nhất chứa một số nguyên là kết quả của bài toán (tổng số luồng xử lý sau khi modulo cho \(10^9 + 7\)).

Example

3

36

Ràng buộc

• Subtask 1 (\(30\%\) số điểm): \(n \le 100\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^6\).
• Subtask 3 (\(40\%\) số điểm): \(n \le 10^{12}\).