Boring Problem

You are given a string $s$ of length $n$. Let's define a function from a string:

Here $|a-b|$ denotes a distance between characters $a$ and $b$ in alphabet. In other words, $f(s)$ denotes sum of $|s_i-s_j|$ over all $1\le i\le j\le n$. Then, let

Here $s[i..j]$ denotes substring of string $s$ from index $i$ to $j$. In other words, $cost(s)$ denotes sum of $f(s[l..r])$ over all $1\le l\le r\le n$.

You are given $q$ queries. Each query changes the element at position $p$ to $c$, i.e., $s_p=c$. You need to print $cost(s)$ mod $1000000007$ before all queries and after each query.

Input

The first line of input contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the string $s$.

The second line of input contains a string $s$ of length $n$.

The third line of input contains a single integer $q$ ($1\le q\le 2\cdot 10^5$) — the number of queries.

The following $q$ lines contain an integer $p$ ($1\le p\le n$) and character $c$ ($c\in \{a,b,\dots ,y,z\}$) — description of queries.

Output

Print $q+1$ integers in separate lines — answers for the problem.

Examples

Scoring

1. ($3$ points): $n\le 3$;

2. ($5$ points): $n,q\le 50$;

3. ($6$ points): $n,q\le 100$;

4. ($7$ points): $c,s_i\in \{a,b\}$;

5. ($20$ points): $n,q\le 5000$;

6. ($21$ points): $n,q\le 20000$;

7. ($13$ points): $c,s_i\le$ "n";

8. ($10$ points): $n,q\le 10^5$;

9. ($15$ points): no additional restrictions.