D. Хүчтэй мод

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

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

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

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

Женос ба Сайтама нар Зул сарын мод авахаар явцгаасан. Гэсэн ч тэдний анхаарлыг өөр төрлийн буюу өндөр Хүчтэй мод татсан.

Хүчтэй мод нь $1$ дугаартай ганц ширхэг үндэс болсон оройгоос эхлэнэ. Хүчтэй мод нь шинэчлэл гэж нэрлэгдэх ид шидийн үзэгдлээр өснө. Шинэчлэлд нэг орой бусад нэг оройн хүүхэд хэлбэрээр модонд нэмэгдэнэ.

Модон дахь бүх орой (үндэс болон бусад бүх нэмэгдсэн оройнууд) үүнтэй холбоотой $v_{i}$ утгатай. Оройн хүч нь уг оройтой холбоотой утга ($v_{i}$) болон шууд холбогдсон хүүхдүүдийн хүчнээс бүрдэх мультсетийн хүчээр тодорхойлогдоно. Мультсетийн хүч мультсетд байгаа бүх элементийн нийлбэрийг үүнд байгаа элементийн тоогоор үржүүлсэнтэй тэнцүү. Өөрөөр бол $S$ мультсетийнх:

Сайтама модонд хийгдэх шинэчлэлүүдийг мэдэж байгаа ба Женосоос ургах үйл явцын турш модны тухай даалгаваруудыг асууж шалгахаар шийдсэн.

Шинэчлэл нь $1 p v$ хэлбэртэй байх ба $v$ утгатай орой $p$ оройн хүүхэд хэлбэрээр нэмэгдэнэ.

Даалгавар нь $2 u$ хэлбэртэй байх ба $u$ оройн хүчийг асууна.

Женод уг даалгаваруудын хариуг $10^{9} + 7$ тоонд хуваагаад гарсан хариуг хариулахад туслана уу.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарласан хоёр бүхэл тоон утга $v_{1}$ ба $q$ ($1 ≤ v_{1} < 10^{9}$, $1 ≤ q ≤ 200 000$) байх ба харгалзан $1$ дугаартай оройн утга ба шинэчлэл болон даалгаваруудын нийт тоо байна.

Дараагийн $q$ мөрөнд шинэчлэлүүд болон даалгаваруудыг агуулна. Эдгээрийн нэг тус бүр нь дараах хэлбэрүүдийн аль нэг байна:

  • $1 p_{i} v_{i}$ байвал энэ мөр шинэчлэлийг тодорхойлно. Нэмэгдсэн оройн дугаар нь модонд ашиглагдаагүй байгаа хамгийн бага эерэг бүхэл тоо байна. Энд $p_{i}$ нь аль хэдийн байгаа орой ба $1 ≤ v_{i} < 10^{9}$ байна.
  • $2 u_{i}$ байвал энэ мөр даалгаварыг тодорхойлно. $u_{i}$ орой нь модонд оршин байх нь тодорхой.

Оролт ядаж нэг даалгавар агуулах нь тодорхой.

Гаралт

Даалгавар бүрийн хувьд өгөгдсөн оройн хүчийг $10^{9} + 7$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
2 5
1 1 3
1 2 5
1 3 7
1 4 11
2 1
Гаралт
344
Оролт
5 5
1 1 4
1 2 3
2 2
1 2 7
2 1
Гаралт
14
94

Тэмдэглэл

Эхний жишээн дээр бүх шинэчлэлийн дараа мод дараах байдлаар байрласан оройнуудтай байна: 1 -- 2 -- 3 -- 4 -- 5

Эдгээр оройнууд харгалзан дараах утгуудтай : 2 -- 3 -- 5 -- 7 -- 11

Харгалзах хүчүүд нь: 344 -- 170 -- 82 -- 36 -- 11

Сэтгэгдлүүдийг ачааллаж байна...