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:
- Dodaj $f(x)$ do swojego wyniku.
- Jeśli $x = 1$, zakończ grę.
- 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$
| Testy | $x$ | $t$ | $x$ jest potęgą liczby pierwszej |
|---|---|---|---|
| $1 \sim 2$ | $\leq 20$ | $\leq 1$ | |
| $3 \sim 4$ | $\leq 10^9$ | ✓ | |
| $5 \sim 6$ | $\leq 10^6$ | ||
| $7 \sim 8$ | $\leq 10^3$ | ||
| $9$ | $\leq 10^{12}$ | ✓ | |
| $10$ | |||
| $11$ | $\leq 10^9$ | $\leq 5\,000$ | ✓ |
| $12$ | $\leq 10^{12}$ | $\leq 10^4$ | |
| $13$ | $\leq 10^9$ | $\leq 5 \times 10^4$ | |
| $14$ | $\leq 10^5$ | ||
| $15$ | $\leq 3\times 10^5$ | ||
| $16$ | ✓ | ||
| $17$ | $\leq 10^{12}$ | $\leq 10^4$ | |
| $18$ | $\leq 5 \times 10^4$ | ||
| $19$ | $\leq 10^5$ | ||
| $20$ | $\leq 3 \times 10^5$ |