Задано массив цілих чисел, спочатку заповнений нулями. Над ним необхідно виконувати два типи операцій:

• ! i x - присвоїти комірці i значення x;
• ? l r - взнати суму значень на відрізку [l, r].

Вхідні дані

Перший рядок містить розмір масиву n та кількість запитів m (1 ≤ n ≤ (109 + 7), 1 ≤ m ≤ 2 * 105). За ним йде m запитів по одному у рядку.

У процесі роботи програми необхідно підтримувати два числа P і Q. Спочатку P = 91, Q = 47.

Запит виду "**! A B**" означає, що у комірку (A + P) mod n необхідно записати число (B + Q) mod (109 + 7).

Запит виду "**? A B**" означає, що необхіно порахувати суму між елементами (A + P) mod n, (B + Q) mod n включно. Нехай відповідь дорівнює Z. Тоді необхідно змінити числа P і Q наступним чином:

P = (P * 31) + Z mod (109 + 7),

Q = (Q * 29) + Z mod (109 + 7).

Нумерація елементів починається з нуля.

Усі вхідні числа не перевищують 109 + 7.

Вихідні дані

Для кождого запиту про суму потрібно вивести відповідь на нього у окремому рядку.