Заданы два массива A и B одинаковой длины. Необходимо обработать три вида запросов.

• * l r x: добавить число x ко всем Ai, где l ≤ i ≤ r.
• . l r x: добавить число x ко всем Bi, где l ≤ i ≤ r.
• ? l r: вычислить сумму Al · Bl + ... + Ar · Br.

Массивы индексируются с 1. Изначально оба массива заполнены нулями.

Входные данные

Первая строка содержит два числа n и m (1 ≤ n, m ≤ 100000) - длины массивов и количество запросов. Следующие m строк содержат запросы в описанном выше формате. В каждом запросе 1 ≤ l ≤ r ≤ n и 1 ≤ x < 109+ 7.

Выходные данные

Для каждого запроса третьего типа вывести в отдельной строке ответ по модулю 109 + 7.