Мала теорема Ферма стверджує, що \textbf{a^p-a} ділиться на \textbf{p} для довільного простого числа \textbf{p} та цілого числа \textbf{a}. У даній задачі мова йтиме про щось схоже. А саме, для заданого натурального числа \textbf{n }> \textbf{1} необхідно знайти усі натуральні \textbf{m} такі, що \textbf{a^n-a} ділиться на \textbf{m} для довільного цілого числа \textbf{a}. Наприклад, для \textbf{n = 2} існує \textbf{2} таких числа: \textbf{1} та \textbf{2}, а для \textbf{n = 3} існує \textbf{4} таких числа: \textbf{1}, \textbf{2}, \textbf{3} та \textbf{6}. Так як таких чисел може бути багато, то потрібно вивести суму усіх таких чисел по модулю \textbf{10^9+7}. Гарантується, что множина таких чисел скінченна для довільного \textbf{n} >\textbf{1}. \InputFile У першому рядку вхідного файлу задано натуральне число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10^5}) -- кількість тестів. У кожному з наступних \textbf{T} рядків задано ціле число \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{2·10^6}). \OutputFile Для кожного числа \textbf{n} з вхідного файлу виведіть у окремому рядку відповідь до задачі.