Remoteland
В Республике Удалённая Земля ежегодно отмечают день независимости. Однако, поскольку это произошло очень давно, никто не помнит точную дату. Единственное, что известно, это то, что сегодня количество дней, прошедших с момента обретения независимости (D), является идеальным квадратом. Более того, это наибольшее возможное число, которое можно представить как произведение различных чисел, не превышающих n.
Поскольку в Удалённой Земле год состоит из 1000000007 дней, жителям нужно узнать D по модулю 1000000007. Обратите внимание, что их интересует именно наибольшее D, а не наибольшее D по модулю 1000000007.
Входные данные
Каждый тестовый случай состоит из одной строки с целым числом n (1 ≤ n ≤ 10000000). Ввод завершается строкой, содержащей 0.
Выходные данные
Для каждого тестового случая выведите количество дней назад, когда Республика стала независимой, по модулю 1000000007, выводя результат для каждого случая на отдельной строке.