E. Ахиад л массив дээрх хүсэлтүүд...

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ элементтэй $a_1, a_2, ..., a_n$ массив өгөгдсөн. Таны даалгавар бол доорх 2 хүсэлтийг хурдан биелүүлэх юм:

  • $l$-ээс $r$ завсарт орших бүх утгыг $x$ болгох. Энэ хүсэлтийн дараагаар $a_l, a_{l + 1}, ..., a_r$ тоонуудын утга бүгд $x$-тэй тэнцүү болох юм.
  • enter image description here ($k$ нь 5-аас хэтрэхгүй ) нийлбэрийг тооцож гаргах. Нийлбэр нь их гарж болзошгүй тул 1000000007 ($10^9 + 7$) хуваахад гарах үлдэгдлийг нь хэвлэ.

Оролт

Эхний мөрөнд массив дахь элементийн тоо $n$ болон хүсэлтийн тоо болох $m$ ($1 ≤ n, m ≤ 10^5$) тоонууд өгөгдөнө. Дараагийн мөрөнд $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^9$) массивын анхны утгууд өгөгдөнө.

Үүний дараагаар $m$ хүсэлт өгөгдөнө:

  • Утга олгох хүсэлт нь дараах форматтай байна: "enter image description here" ($1 ≤ l ≤ r ≤ n; 0 ≤ x ≤ 10^9$).
  • Нийлбэр олох хүсэлт нь дараах форматтай байна: "enter image description here" ($1 ≤ l ≤ r ≤ n; 0 ≤ k ≤ 5$).

Оролтны бүх тоо $2^{31} - 1$ дотор багтана.

Гаралт

Нийлбэрийг тооцоолох хүсэлт бүрт хариуг нь 1000000007 ($10^9 + 7$) хуваахад гарах үлдэгдлийг хэвлэ.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
4 5
5 10 2 1
? 1 2 1
= 2 2 0
? 2 4 3
= 1 4 1
? 1 4 5
Гаралт
25
43
1300
Оролт
3 1
1000000000 1000000000 1000000000
? 1 3 0
Гаралт
999999986
Сэтгэгдлүүдийг ачааллаж байна...