Sequence Operations and Trailing Fives

You are given a sequence \( A = \{a_1, a_2, \dots, a_n\} \) where each \( a_i \) is a digit in the range [0, 9].

For any contiguous subsequence from index \( l \) to \( r \) (\( 1 \le l \le r \le n \)), define the function \[ f(l,r)=\text{the number of consecutive }5\text{'s at the end of }\overline{a_l a_{l+1} \dots a_r}. \] For example, if \( A = \{1,1,4,5,1,4\} \), then \( f(2,4)=1 \) since the number formed by \( a_2,a_3,a_4 \) is 145 which ends with one 5; and \( f(1,3)=0 \) because 114 does not end with a 5.

The sequence will undergo a series of operations. There are four types of operations:

• 1 x y: Set the \( x \)th element of \( A \) to \( y \) (\( y \) is in [0, 9]).
• 2: Reverse the entire sequence \( A \). For example, reversing \( \{1,1,4,5\} \) yields \( \{5,4,1,1\} \).
• 3: Query the value of \[ Q_3 = \left(\sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r)\right) \bmod (10^9+7). \] Output the result of this query.
• 4 l r: Query the value of \[ Q_4 = \left(\sum_{i=l}^{r} a_i\right) \bmod (10^9+7). \] Output the result of this query.

The input begins with two integers \( n \) and \( m \) representing the length of the sequence and the number of operations respectively. The next line contains \( n \) space-separated digits representing the sequence \( A \). Each of the following \( m \) lines describes an operation in one of the four formats above.

inputFormat

The first line contains two integers \( n \) and \( m \) --- the number of elements in the sequence and the number of operations, respectively.

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \) where \( 0 \le a_i \le 9 \).

Each of the next \( m \) lines describes an operation in one of the following formats:

• 1 x y: Update operation: set \( a_x = y \).
• 2: Reverse the sequence.
• 3: Query the sum of \( f(l,r) \) over all \( 1 \le l \le r \le n \): output \( \left(\sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r)\right) \bmod (10^9+7) \).
• 4 l r: Query the sum of the subsequence from index \( l \) to \( r \): output \( \left(\sum_{i=l}^{r} a_i\right) \bmod (10^9+7) \).

outputFormat

For each query operation (types 3 and 4), output the result on a new line.

sample

6 4
1 1 4 5 1 4
3
4 2 5
2
3

4
11
3