Ngày xửa ngày xưa tại một vương quốc xa xôi, nơi quốc vương và các thần dân hằng năm đều tổ chức kỷ niệm ngày độc lập. Tuy nhiên đã từ rất lâu rồi, không ai còn nhớ chính xác ngày độc lập là ngày nào. Điều duy nhất mà họ nhớ là cho tới hôm nay, số ngày đã trôi qua tính từ ngày độc lập là một số chính phương ~D~. Hơn nữa, đây là số lớn nhất có thể mà có thể phân tích thành tích các số nguyên dương phân biệt nhỏ hơn hoặc bằng ~N~.

Một năm ở vương quốc có ~ 10^9 ~ ngày, vậy nên người dân chỉ cần số ~D~ mod ~10^9+7~. Chú ý rằng cần tìm số ~D~ lớn nhất, không phải là (~D~ mod ~10^9+7~) lớn nhất.

Input

• Gồm nhiều test, mỗi test miêu tả bởi một dòng duy nhất chứa số nguyên dương N (~ N \le 10^7 ~). Dữ liệu kết thúc bởi một dòng chứa số 0.

Output

• Với mỗi test in ra kết quả trên một dòng số ~ D Mod 10^9+7 ~.

Sample

Input #1

4
9348095
6297540
0

Output #1

4
177582252
644064736

Problem source: ĐỀ KIỂM TRA ĐỘI TUYỂN HSG LẦN 2 Day 2- Hải Phòng 2020