1397: Кількість прямокутників


Submit solution


Points:9
Time limit:1.0s
Memory limit:62M
Author:

Problem type

Василько придумав інтелектуальну гру. Він розглядає квадратну таблицю розмірності N. Всі клітинки (x,y), які задовольняють умову x*y≤N він зафарбував. Тепер він рахує всі можливі прямокутники, що містять зафарбовані клітинки і не містять не фарбованих.

Наприклад, при N=4 зафарбованими будуть такі клітинки: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (3,1), (4,1).

Василько хоче точно знати скільки є всього можливих варіантів прямокутників, які містять лише зафарбовані клітинки. Допоможіть йому.

Оскільки це число може бути досить великим, то треба вивести його по модулю 1000000007.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число Т (1 ≤ T ≤ 5) — кількість тестів.

Єдиний рядок кожного тесту містить ціле N (1 ≤ N ≤ 10^10).

Формат вихідних даних

Для кодного тесту вивести шукану кількість прямокутників по модулю 1000000007.

Приклад вхідних даних

2
4
10000000000

Приклад вихідних даних

23
227374950

Comments

There are no comments at the moment.