## Kuon

The name of the heroine in this story is Kuon(久遠). Kuon has the similar meaning to "long-term and persistent", so the problem is about the persistent data structure.

For a set with only natural numbers, we define $mex(S)= \min \{x | x \in N \land x \notin S\}$.

Kuon has a emptyset $Y = \emptyset$ initialy.

She'll implement $n$ operations, where the $i$-th operation is:

1. She'll change Y to the set after the $c_i$-th operation(Y at that time when the $c_i$-th operation has been done and the $c_{i+1}$-th operation hasn't been done), or the initial set $\emptyset$ if $c_i = 0$.

2. Let $Y= Y \cup \lbrace v_i \rbrace$.

3. Query the value of $mex(Y)$.

The first line contains an integer representing $n(1 \le n \le 5*10^6)$.

In order to prevent your submissions from TLE during the input phase, $c_i(0 \le c_i < i),v_i(0 \le v_i \le 10^9)$ are represented in base-64. Here we use $a, b, c, \cdots, z, A, B, C, \cdots, Z, 0, 1, 2, \cdots, 9, !, ?$ to represent the smallest , the second smallest, the third smallest, $\cdots$, the $64-th$ smallest value in base-64, respectively.

The second line contains a string whose length is $4n$. $c_i$ is represented by the $(4i-4)-th$ character to the $(4i-1)-th$ character.

The third line contains a string whose length is $5n$. $v_i$ is represented by the $(5i-5)-th$ character to the $(5i-1)-th$ character.

In order to prevent your submissions from TLE during the output phase, suppose that $ans_i​$ is the value of $mex(Y)​$ in the $i​$th operation.

You need to output $(\sum_{i=1}^n ans_i \times 1990214^i) \mod 1000000009$.

3
aaaaaaabaaac
aaaaaaaaabaaaac
896388709

In sample case, $c_1 = 0, c_2 = 1, c_3 = 2, v_1 = 0, v_2 = 1, v_3 = 2$, and $ans_1 = 1, ans_2 = 2, ans_3 = 3$.

So the output should be $(1\times 1990214 + 2\times 1990214^2 + 3\times 1990214^3) \mod 1000000009 = 896388709$.

Also, please be careful of stack overflow.

2018 fdupc

2018 FDUPC 程序设计校赛现场赛（网络同步赛）