У вас є масив. Спочатку вiн зовсiм малесенький – cкладається всього з одного числа.

Та з кожним запитом вiн ставатиме все бiльшим i бiльшим. Чи впораєтеся ви з цим масивом i запитами на ньому? Формальніше, вам необхідно обробити такі запити:

• COPY – скопіювати масив та додати його в кінець
• CHANGE pos val – замінити значення в позиції pos на val
• SUM left right – обчислити суму всіх елементів на відрізку [left;right] за модулем 109+7

Вхідні дані

У першому рядку вхідних даних міститься єдине число A (1 ≤ A ≤ 109) - єдиний елемент масиву

У другому рядку задано число Q(1 ≤ Q ≤ 2*105) – кількість запитів.

В наступних Q запитів в наступному форматі :

• COPY – запит першого типу
• CHANGE pos val – запит другого типу (1 ≤ pos ≤ 1018 ,1 ≤ val ≤ 109)
• SUM left right – запит третього типу (1 ≤ left ≤ right ≤ 1018) Гарантується, що pos, left, right із другого і третього запитів не перевищують поточний розмір масиву.

Вихідні дані

Для кожного запиту третього типу виведіть єдине число – суму всіх чисел на відповідному відрізку за модулем 109+7.