C. Блак Видов

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

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

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

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

Наталиа Романова S.H.I.E.L.D-ээс түүнд өгсөн шинэ буун дээр нэгэн туршилт явуулахыг оролдож байв. Уг туршилтын үр дүнг тодорхойлохын тулд тэрээр нэгэн өгөгдсөн тэгшитгэлийн хариултыг олох хэрэгтэй юм. Уг тэгшитгэл нь дараах хэлбэртэй байна:

Энд нь логикийн OR үйлдлийг илэрхийлэх ба нь логикийн онцгой OR үйлдэл буюу XOR үйлдлийг илэрхийлэх бөгөөд $v_{i, j}$-ууд нь бүүлийн хувьсагчууд(boolean variables) эсвэл тэдгээрийн үгүйсгэлүүд байх юм. Наталиа тэгшитгэлийн зүүн талыг XNF томьёо гэж нэрлэх бөгөөд хаалтан дотор байгаа илэрхийлэл болгоныг байц, $v_{i, j}$ болгоныг үсгийн алдаанууд гэж нэрлэнэ.

Наталиа-д байгаа тэгшитгэлийн хувьд тэгшитгэлийн зүүн тал нь яг үнэндээ $x_{1}, x_{2}, ..., x_{m}$ гэсэн хувьсагчууд болон эдгээрийн үгүйсгэлийг агуулах 2-XNF-2 байжээ. Хэрэв дараах нөхцөлүүдийг хангаж байвал XNF томьёо нь 2-XNF-2 болно. Үүнд:

  1. $1 ≤ i ≤ n$ бүрийн хувьд $k_{i} ≤ 2$ байна. Өөрөөр хэлбэл байц болгоны хэмжээ нь 2-оос хэтрэхгүй байна.
  2. Томьёонд хувьсагч болгон нь хамгийн ихдээ 2 удаа гарч ирнэ(өөрийн үгүйсгэл болон өөрийнх нь гарч ирсэн тоо нь нийтдээ хамгийн ихдээ 2 байна). Ямар нэгэн хувьсагч нь 2 удаа гарч ирэх боломжтой бөгөөд энэ тохиолдолд түүний үгүйсгэл нь ямар ч байц дотор гарч ирсэн байж болохгүйг анхаарна уу(мөн эсрэгээрээ ижил байхыг анхаарна уу).

Наталиа-д $m$ ширхэг хувьсагчид болон $n$ ширхэг байцаас тогтох нэгэн томьёо өгөгджээ. Томьёо нь хэрхэн харагддаг болохыг сайтар ойлгохын тулд жишээнүүдийг сайтар харна уу.

Наталиа онол судалгаанаас илүүтэйгээр тулалдах тал дээр сайн учраас энэ удаад тэрээр танаас уг тэгшитгэлийн хариултын тоог хэлж өгөхийг хүсжээ. Илүү тодруулбал, та уг тэгшитгэлийг хангаж байх $үнэн$ болон $худал$ гэсэн $x_{1}, ..., x_{m}$-уудын олонлогуудын тоог (нийт $2^{m}$ ширхэг боломжит олонлог байна) олох юм. Энд эдгээр хувьсагчуудын утга нь $үнэн$ эсвэл $худал$($true$ and $false$) байх юм. Нэгэнт уг тоо нь маш том тоо байж болох учраас та хариултаа $10^{9} + 7$ модулаар бодон хэвлэнэ үү.

Зарим хувьсагч нь нэг байц дотор 2 удаа гарч ирсэн байж болох ба эсвэл томьёон дотор огт гарч ирээгүй ч байсан байж болохыг анхаарна уу. Тэгсэн хэдий ч уг хувьсагчид $үнэн$ эсвэл $худал$ гэсэн утга өгөх нь хувьсагчдын утгыг сонгох ялгаатай арга зам үүсгэх юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 100 000$) өгөгдөх ба эдгээр нь харгалзан байцын тоо болон хувьсагчдын тоог тус тус илэрхийлнэ.

Дараагийн $n$ мөрөнд томьёо өгөгдөнө. Эдгээр мөрүүдийн $i$-дахь мөр нь $k_{i}$ гэсэн бүхэл тоогоор эхлэх бөгөөд энэ нь $i$-дахь байц доторх үсгийн алдаануудын тоог илэрхийлэх юм. Үүний дараа уг мөрөнд $k_{i}$ ширхэг тэгээс ялгаатай бүхэл тоонууд $a_{i, 1}, ..., a_{i, k_{i}}$-ууд өгөгдөнө. Хэрэв $a_{i, j} > 0$ байвал $v_{i, j}$ нь $x_{a_{i, j}}$ болох ба бусад тохиолдолд $x_{ - a_{i, j}}$-ын үгүйсгэл болох юм ($1 ≤ k_{i} ≤ 2$, $ - m ≤ a_{i, j} ≤ m$, $a_{i, j} ≠ 0$).

Гаралт

Хариултыг $1 000 000 007$ ($10^{9} + 7$) модулаар бодон нэг мөрөнд хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
6 7
2 4 -2
2 6 3
2 -7 1
2 -5 1
2 3 6
2 -2 -5
Гаралт
48
Оролт
8 10
1 -5
2 4 -6
2 -2 -6
2 -7 9
2 10 -1
2 3 -1
2 -8 9
2 5 8
Гаралт
544
Оролт
2 3
2 1 1
2 -3 3
Гаралт
4

Тэмдэглэл

Эхний жишээний тэгшитгэл нь дараах байдалтай байна:

2-дахь жишээний тэгшитгэл нь дараах байдалтай байна:

3-дахь жишээний тэгшитгэл нь дараах байдалтай байна:

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