E. Бүүлен функц

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

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

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

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

Энэ бодлогон дээр бид $A, B, C, D$ дөрвөн хувьсагчдын Бүүлен функцүүдийг авч үзнэ. $A, B, C, D$ хувьсагчууд нь логик ба 0 эсвэл 1 утгыг авч чадна. Бид функцийг дараах дүрмийг ашиглан тодорхойлно:

<илэрхийлэл> ::= <хувьсагч> | (<илэрхийлэл>) <оператор> (<илэрхийлэл>)

<хувьсагч> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

<оператор> ::= '&' | '|'

Энд $A, B, C, D$ том үсгүүд нь хувьсагчуудыг илэрхийлэх ба жижиг үсгүүд нь эдгээрийн инверсийг илэрхийлнэ. Жишээлбэл хэрвээ $A = 1$ байвал $'A'$ тэмдэгт 1 гэсэн утгатай харгалзах ба $'a'$ тэмдэгтийн утга 0 гэсэн утгатай харгалзана. Энд '&' тэмдэгт нь логик AND үйлдэлтэй харгалзах ба '|' тэмдэгт нь логик OR үйлдэлтэй харгалзана.

Танд зарим үйлдлүүд болон хувьсагчууд нь дутуу $f$ функцийг тодорхойлох $s$ илэрхийлэл өгөгдсөн. Мөн та $n$ ялгаатай хувьсагчын утгуудын бүрдлийн хувьд $f(A, B, C, D)$ функцийн утгуудыг мэдэж байгаа. Илэрхийлэлд дутаж байгаа элементүүдийг сэргээх замуудын тоог тоол мөн гарч буй илэрхийлэл нь өгөгдсөн хувьсагчуудын бүрдэл дахь $f$ функцийн тухай мэдээлэлтэй харгалзана. Гаралтын утга маш том тоо байж болох учир $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд илэрхийлэл $s$ ($1 ≤ |s| ≤ 500$) байх ба зарим and/or операторууд болон хувьсагчууд '?' тэмдэгтээр солигдсон байна.

Хоёр дахь мөрөнд $n$ ($0 ≤ n ≤ 2^{4}$) тоо байх ба бидний $f(A, B, C, D)$ функцийн утгыг мэдэж байгаа бүхэл тоон утгуудын бүрдлүүдийн тоо юм. Дараагийн $n$ мөрөнд бүрдлүүдийн тодорхойлолтууд байна: эдгээрийн $i$-р мөр бүр зайгаар тусгаарлагдсан таван бүхэл тоон утга $a_{i}, b_{i}, c_{i}, d_{i}, e_{i}$ ($0 ≤ a_{i}, b_{i}, c_{i}, d_{i}, e_{i} ≤ 1$) байх ба $f(a_{i}, b_{i}, c_{i}, d_{i}) = e_{i}$ байна.

Бүх ($a_{i}, b_{i}, c_{i}, d_{i}$) хослолууд ялгаатай байх нь тодорхой.

Гаралт

Бодлогын хариуг нэг мөрөнд хэвлэ.

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

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

Оролт
?
2
1 0 1 0 1
0 1 1 0 1
Гаралт
2
Оролт
(A)?(?)
1
1 1 0 0 0
Гаралт
4
Оролт
((?)&(?))|((?)&(?))
0
Гаралт
4096
Оролт
b
1
1 0 1 1 1
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр хүчинтэй хоёр илэрхийлэл нь 'C' ба 'd' байна.

Хоёр дахь жишээн дээр илэрхийллүүд нь дараах байдалтай харагдана: '(A)&(a)', '(A)&(b)', '(A)&(C)', '(A)&(D)'.

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