J. Phantom Poker
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alex loves poker! Unfortunately, today all the players in his home game have transformed into ghosts and ghouls. Also, instead of a standard 52-deck, there are $$$n$$$ cards in a row, each with one of the thirteen ranks. For simplicity, all the ranks are integers from $$$1$$$ to $$$13$$$.

Alex soon discovers that the spirits really love "phantom" combinations, which are defined to be combinations of cards whose product of denominations is $$$5 \bmod 13$$$. For example, a $$$2$$$, $$$5$$$, and $$$7$$$ is a "phantom" combination since $$$2 \cdot 5 \cdot 7 = 70$$$, which is $$$5 \bmod 13$$$.

As Alex gets up to leave, he is met with $$$q$$$ different challenges! On each challenge, the ghoul asks two types of queries:

  • 1 i x ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 13$$$) — Set the rank of the $$$i$$$th card to $$$x$$$.
  • 2 l r ($$$1 \leq l \leq r \leq n$$$) — Find the number of phantom combinations of cards using only the cards from indices $$$l$$$ to $$$r$$$, inclusive.
Note that for query two, cards at different indices are considered distinct, even if they have the same rank.

Alex is stunned; how is he going to leave now? Can you help him process each of the queries? The answers for query 2 may be large, so output the answer $$$\bmod 10^9 + 7$$$.

Input

The first line contains two space separated integers, $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^4$$$) — the number of total cards and the number of queries that need to be processed.

The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \leq d_i \leq 13$$$) — the initial ranks of each cards.

The next $$$q$$$ lines contain a query, one per each line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type print the answer for it – the number of possible phantom combinations of cards using only cards within the specified range.

Example
Input
4 3
1 2 5 9
2 1 4
1 2 3
2 1 3
Output
4
2