Нудна задача

Дано рядок $s$ довжини $n$. Визначимо функцію від рядка:

Тут $|a-b|$ позначає відстань між символами $a$ та $b$ в алфавіті. Іншими словами, $f(s)$ позначає суму $|s_i-s_j|$ для всіх $1\le i\le j\le n$. Далі, визначимо

Тут $s[i..j]$ позначає підрядок рядка $s$ від індексу $i$ до $j$. Іншими словами, $cost(s)$ позначає суму $f(s[l..r])$ для всіх $1\le l\le r\le n$.

Дано $q$ запитів. Кожен запит змінює елемент на позиції $p$ на $c$, тобто робить $s_p=c$. Вам потрібно вивести $cost(s)$ mod $1000000007$ перед усіма запитами та після кожного запиту.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) — довжину рядка $s$.

Другий рядок містить рядок $s$ довжини $n$.

Третій рядок містить одне ціле число $q$ ($1\le q\le 2\cdot 10^5$) — кількість запитів.

Наступні $q$ рядків містять ціле число $p$ ($1\le p\le n$) та символ $c$ ($c\in \{a,b,\dots ,y,z\}$) — опис запитів.

Вихідні дані

Виведіть $q+1$ цілих чисел в окремих рядках — відповіді на задачу.

Приклади

Оцінювання

1. ($3$ бали): $n\le 3$;

2. ($5$ балів): $n,q\le 50$;

3. ($6$ балів): $n,q\le 100$;

4. ($7$ балів): $c,s_i\in \{a,b\}$;

5. ($20$ балів): $n,q\le 5000$;

6. ($21$ бал): $n,q\le 20000$;

7. ($13$ балів): $c,s_i\le$ "n";

8. ($10$ балів): $n,q\le 10^5$;

9. ($15$ балів): без додаткових обмежень.