Số chính phương là một loại số rất quen thuộc đối với chúng ta. Do đó, duong3982 muốn tổ chức một trò chơi liên quan tới con số này.

Nhắc lại: Một số ~x~ nguyên dương được định nghĩa là số chính phương nếu tồn tại một giá trị ~k~ nguyên dương mà ~k \times k = x~.

Bạn được phát ~n~ viên bi, đánh số từ ~1~ tới ~n~, viên bi thứ ~i~ mang giá trị sức mạnh là ~i~. Bạn được quyền chọn một tập viên bi từ ~n~ viên bi trên, sao cho không tồn tại tích của hai giá trị sức mạnh bất kỳ trong tập viên bi đó có tích là một số chính phương.

Yêu cầu: Hãy đếm số cách chọn tập bi từ ~n~ viên bi trên. Lưu ý, cần tính cả tập rỗng.

INPUT

Nhập vào số nguyên ~n~ (~n \le 5 \times 10^6~).

OUTPUT

In ra đáp số bài toán khi chia lấy dư cho ~10^9 + 7~.

SAMPLE INPUT 1

3

SAMPLE OUTPUT 1

8

SAMPLE INPUT 2

10

SAMPLE OUTPUT 2

384