Обратите внимание на необычное ограничение по памяти.
Есть \(n\) поваров, пронумерованных \(1, 2, \ldots, n\), которые готовят блюда для короля. Повар \(i\) обладает мастерством \(i\) и первоначально приготовил блюдо вкусности \(a_i\), где \(|a_i| \leq i\). У каждого повара есть список поваров, блюда которых он может копировать. Чтобы не допускать распространение плохих привычек, король гарантирует, что повар \(i\) может копировать только у поваров с более высоким мастерством.
Повара работают над своими блюдами в течение нескольких дней. Каждый день работа над блюдом разбивается на два этапа.
- В начале каждого дня каждый повар может выбрать, поработать или нет над своим блюдом, тем самым умножая вкусность своего блюда на свое мастерство (\(a_i := i \cdot a_i\)).
- После того как все (кто хотел) поработали над своими блюдами, каждый повар начинает изучать работу других поваров. А именно, для каждого повара \(j\) из списка повара \(i\), повар \(i\) может выбрать, скопировать ли блюдо повара \(j\), тем самым прибавляя вкусность блюда \(j\) к своему \(i\)-му блюду (\(a_i := a_i + a_j\)). Можно считать, что все копирования происходят одновременно. Иначе говоря, если повар \(i\) хочет скопировать блюдо повара \(j\), он скопирует вкусность блюдо повара \(j\), полученную в конце этапа \(1\).
Чтобы угодить королю, каждый повар стремятся максимизировать вкусность своего блюда.
Наконец, вам заданы \(q\) запросов. Каждый запрос одно из двух видов:
- \(1\) \(k\) \(l\) \(r\) — посчитайте сумму вкусностей \(a_l, a_{l+1}, \ldots, a_{r}\) по окончании \(k\)-го дня. Так как данное значение может быть велико, выведите его по модулю \(10^9 + 7\).
- \(2\) \(i\) \(x\) — король дарит \(x\) единиц вкусности блюду \(i\)-го повара перед началом \(1\)-го дня (\(a_i := a_i + x\)). Заметим, что королю нравятся вкусные блюда, а потому он дарит положительную вкусность (\(x > 0\)).
Обратите внимание, что запросы типа \(1\) не зависят от других запросов. Точнее говоря, каждый запрос типа \(1\) — это только возможный сценарий и он не меняет вкусности \(a_i\) для запросов далее. При этом запросы типа \(2\) накапливаются, но меняют только первоначальные значения \(a_i\) блюд. В примечании представлены примеры запросов.
Выходные данные
Для каждого запроса первого вида выведите одно число — ответ на этот запрос.
Примечание
Ниже показаны множества поваров, у которых может копировать каждый из поваров в примере.
- \(1\): \(\{2, 3, 4, 5\}\)
- \(2\): \(\{3\}\)
- \(3\): \(\{4\}\)
- \(4\): \(\{5\}\)
- \(5\): \(\emptyset\) (ни у кого)
Далее следует описание первого примера.
Для первого запроса вида \(1\) первоначальные значения вкусностей равны \([1, 0, -2, -2, 4]\).
Значения вкусностей после каждого этапа в первый день:
- \([1, 0, -2, -2, 20]\) (повар \(5\) работает над своим блюдом).
- \([21, 0, -2, 18, 20]\) (повар \(1\) и повар \(4\) копируют у повара \(5\)).
Таким образом, ответ на \(1\)-й запрос равен \(21 + 0 - 2 + 18 + 20 = 57\).
Для \(5\)-го запроса (\(3\)-й вида \(1\)), первоначальные значения вкусностей теперь равны \([1, 0, 0, 1, 4]\).
День 1
- \([1, 0, 0, 4, 20]\) (повара \(4\) и \(5\) работают над своими блюдами).
- \([25,0, 4, 24, 20]\) (повар \(1\) копирует у поваров \(4\) и \(5\), повар \(3\) копирует у повара \(4\), повар \(4\) копирует у повара \(5\)).
День 2
- \([25, 0, 12, 96, 100]\) (все, кроме повара \(2\) работают над своими блюдами).
- \([233, 12, 108, 196, 100]\) (повар \(1\) копирует у поваров \(3\), \(4\) и \(5\), повар \(2\) у \(3\), повар \(3\) у \(4\), повар \(4\) у повара \(5\)).
Таким образом, ответ на \(5\)-й запрос равен \(12+108+196=316\).
Можно показать, что на каждом описанном шаге все повара действовали оптимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 0 -2 -2 4
4 2 3 4 5
1 3
1 4
1 5
0
7
1 1 1 5
2 4 3
1 1 1 5
2 3 2
1 2 2 4
2 5 1
1 981 4 5
|
57
71
316
278497818
|