You've got an array, consisting of *n* integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. Your task is to quickly run the queries of two types:
1.  Assign value *x* to all elements from *l* to *r* inclusive. After such query the values of the elements of array *a*<sub class="lower-index">*l*</sub>, *a*<sub class="lower-index">*l* + 1</sub>, ..., *a*<sub class="lower-index">*r*</sub> become equal to *x*.1.  Calculate and print sum <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/920d5e77b57e41992ceefa42465edf8cfc006a39.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *k* doesn't exceed 5. As the value of the sum can be rather large, you should print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">5</sup>), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains *n* integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the initial values of the array elements.

Then *m* queries follow, one per line:
1.  The assign query has the following format: "<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/b2ef693fd11e9e29c50f180848ea668ed6d33b22.png" style="max-width: 100.0%;max-height: 100.0%;"/>", (1 ≤ *l* ≤ *r* ≤ *n*; 0 ≤ *x* ≤ 10<sup class="upper-index">9</sup>).1.  The query to calculate the sum has the following format: "<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6a63948f42b361ef379406ad9a679d1da1aee76b.png" style="max-width: 100.0%;max-height: 100.0%;"/>", (1 ≤ *l* ≤ *r* ≤ *n*; 0 ≤ *k* ≤ 5).
All numbers in the input are integers.
from typing import Tuple


class SingleManager:
    def __init__(
        self,
    ) -> None:
        self.stack = []
        self.min = 0

    def open(self, i: int):
        self.stack.append(i)

    def close(self, i: int):
        if self.stack:
            self.stack.pop(-1)+1
        else:
            self.min = i

    def low(self) -> int:
        if self.stack:
            return self.stack[-1]
        return self.min

    def process(self, i: int, c: str):
        if c in "({[":
            self.open(i)
        else:
            self.close(i)


class TripleManager:
    def __init__(self) -> None:
        self.ans = 0
        self.n = 1
        self.managers = []

    def process(self, s: str) -> Tuple[int, int]:
        self.ans = 0
        self.n = 1

        self.managers = [SingleManager(), SingleManager(), SingleManager()]

        for i, c in enumerate(s):
            if c in "()":
                self.managers[0].process(i+1, c)
            if c in "{}":
                self.managers[1].process(i+1, c)
            if c in "[]":
                self.managers[2].process(i+1, c)

            cur = min([i+1 - m.low() for m in self.managers])
            if cur > 0 and cur == self.ans:
                self.n += 1
            if cur > self.ans:
                self.ans = cur
                self.n = 1
        return self.ans, self.n


print(*TripleManager().process(input()))
