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.