Jak wiadomo, Rikka nie jest zbyt dobra z matematyki, więc Yuta zaczął uczyć ją pewnej gry. Na początku mamy liczbę całkowitą $x$. Każda liczba ma przypisaną „punktację” $f(x)$. Proces gry przebiega następująco:

1. Dodaj $f(x)$ do swojego wyniku.
2. Jeśli $x = 1$, zakończ grę.
3. W przeciwnym razie wybierz losowo liczbę pierwszą $p|x$ i podziel $x$ przez $p$. Następnie wróć do kroku pierwszego.

Jaka jest wartość oczekiwana wyniku? Odpowiedź należy podać modulo $P = 10^9 + 7$.

Aby trenować umiejętności obliczeniowe Rikki, Yuta chce, aby odpowiadała na jego pytania tak szybko, jak to możliwe. Dodatkowo, przy każdym kolejnym pytaniu Yuta zmienia wartość jednego z $f$. Oczywiście to zadanie jest zbyt trudne dla uroczej Rikki, czy możesz jej pomóc?

Wejście

Pierwsza linia zawiera dwie liczby całkowite $x$ oraz $t$, oznaczające wartość początkową oraz liczbę pytań (początkowy stan $f$ również traktowany jest jako pytanie).

W kolejnej linii znajduje się $d(x)$ liczb ($d(x)$ oznacza liczbę dzielników $x$), gdzie $i$-ta liczba oznacza punktację $f(v)$ dla $i$-tego najmniejszego dzielnika $v$ liczby $x$.

Następnie $t - 1$ linii zawiera po dwie liczby $v$ oraz $y$, przy czym $v|x$. Oznaczają one zmianę wartości $f(v)$ na $y$. Zmiany są trwałe.

Wyjście

Wypisz $t$ linii, z których każda zawiera odpowiedź na kolejne pytanie (początkowy stan $f$ oraz stany po każdej z $t-1$ modyfikacji).

Przykład

Przykład 1

Wejście

6 1
1 2 4 8

Wyjście

12

Uwagi

W pierwszym kroku Rikka może podzielić 6 przez 2 lub 3, jednak w następnym kroku zawsze otrzyma 1. Zatem z równym prawdopodobieństwem zachodzą dwa procesy: 6 → 3 → 1 lub 6 → 2 → 1. Wyniki dla tych procesów to odpowiednio 13 i 11, więc wartość oczekiwana wynosi 12.

Podzadania

Dla 100% danych: $1\le x \le 10^{12}, 1\le t \le 3 \times 10^5, 1\le f(v),y \le 10^9$