Как известно, у Рикки не очень хорошо с математикой, поэтому Юта начал учить её играть в игру. Изначально дано целое число $x$. У каждого числа есть «счёт», который мы обозначим как $f(x)$. Далее выполняется следующий процесс:

1. К текущему счёту прибавляется $f(x)$.
2. Если $x = 1$, игра заканчивается.
3. В противном случае случайным образом выбирается простое число $p$, такое что $p|x$, и $x$ делится на $p$. Затем процесс возвращается к первому шагу.

Чему равно математическое ожидание счёта? Ответ выведите по модулю $P = 10^9 + 7$.

Чтобы натренировать вычислительные способности Рикки, Юта хочет, чтобы она отвечала на его вопросы как можно быстрее, при этом после каждого вопроса Юта изменяет значение некоторого $f$. Конечно, для милой Рикки эта задача слишком сложна, не могли бы вы ей помочь?

Входные данные

В первой строке записаны два целых положительных числа $x$ и $t$, обозначающие начальное значение и количество вопросов (начальное состояние $f$ также считается за один вопрос).

В следующей строке записаны $d(x)$ чисел ($d(x)$ — количество делителей числа $x$), где $i$-е число обозначает счёт $f(v)$ для $i$-го по возрастанию делителя $v$ числа $x$.

Далее следуют $t - 1$ строк, каждая из которых содержит два числа $v$ и $y$, где гарантируется, что $v|x$. Это означает изменение значения $f(v)$ на $y$. Изменения являются постоянными.

Выходные данные

Выведите $t$ строк, содержащих ответы на каждый вопрос (начальное состояние $f$ и состояния после каждого из $t-1$ изменений).

Примеры

Пример 1

Входные данные

6 1
1 2 4 8

Выходные данные

12

Примечание

В первый раз Рикка может разделить 6 на 2 или на 3, однако на следующем шаге она неизбежно получит 1. Таким образом, с равной вероятностью происходят два процесса: 6 → 3 → 1 или 6 → 2 → 1. Ответы для этих двух процессов равны 13 и 11 соответственно, поэтому ожидание равно 12.

Подзадачи

Для 100% данных: $1\le x \le 10^{12}, 1\le t \le 3 \times 10^5, 1\le f(v),y \le 10^9$.