You are given an array $A$ of length $N$. A pair $(a,\ b)$ is considered good if the following criterion is fulfilled:

Consider the decimal representation of $a$ and $b$. $a$ has digits $a_{1},a_{2},...,a_{k1}$ and $b$ has digits $b_{1},b_{2},...,b_{k1}$. $(a,\ b)$ is good only if there is no index $y\ (1 \le y \le k)$ such that $a_{y}$ and $b_{y}$ are non-zero elements.

You are required to process $Q$ queries where each having one of the following forms:

$0 \, i \, x$: Change the $i^{th}$ index to x in the array
$1 \, l \, r$: Consider all the pairs $(i,\ j)$ such that $l \le i \le j \le r$ such that $(a_{i},\ a_{j})$ is a good pair and add $a_{i} \prod a_{j}$ to the answer.
Note: As the answer can be large, print answer modulo $10^{9} + 7$.

Input format

• First line: An integer $N$ ($1 \le N \le 10^{5}$) representing the length of the array
• Second line: $N$ space-separated integers that representing the elements of the array ($0 \le A_{i} \le 999999$)
• Next $q$ lines: One of the queries of the following forms:
  • $0 \, i \, x$ ($1 \le i \le N,\ 0 \le x \le 999999$)
  • $1 \, l \, r$ ($1 \le l \le r \le N$)

Output format

For each query of type $1$, print the required answer in a separate line.