eolymp
bolt
Try our new interface for solving problems
Məsələlər

Testing Circuits

Testing Circuits

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

A Boolean expression is given. In the expression, each variable appears exactly once. Calculate the number of variable assignments that make the expression evaluate to true.

Giriş verilənləri

A data set consists of only one line. The Boolean expression is given by a string which consists of digits, x, (, ), |, , and  . Other characters such as spaces are not contained. The expression never exceeds 1,000,000 characters. The grammar of the expressions is given by the following BNF.

::=  |  "|"
::=  |  "&"
::=  | "~"  | "("  ")"
::= "x"
::= "1" | "2" |... | "999999" | "1000000"

The expression obeys this syntax and thus you do not have to care about grammatical errors. When the expression contains N variables, each variable in {x1, x2, ..., xN} appears exactly once.

Çıxış verilənləri

Output a line containing the number of variable assignments that make the expression evaluate to true in modulo 1,000,000,007.

Nümunə

Giriş verilənləri #1
x1&~~x2&x3&~x4&~~x5|~~x6|~~x7&(~x8&~x9|~~x10|~~x11&~x12&(~x13&x14&~~x15|~~x16)|(~x17&~~x18|x19)&x20)&~x21&~x22&~~x23|x24&x25|~~x26|~~x27&x28|x29&~x30&(~~x31|x32&(~~x33|(~x34|x35|x36|(~~x37|~x38&x39)&x40)|(x41&(~~x42|~~x43&~~x44)&~~x45|x46&(x47|x48&~x49|(~~x50&~x51&~x52|x53&x54)|~~x55)&~x56|~x57|~x58&(~x59&x60&~~x61&~~x62)&x63&~x64&~x65|x66&~x67&(~x68&(~x69&x70&x71&x72&~x73&(~~x74|~~x75|~~x76|~~x77|x78&(~x79|(~~x80&~~x81&x82|(x83&x84&~x85&x86)|~x87&x88&(~~x89|x90|x91&~x92|~~x93&(~x94&~x95)&(~x96&~~x97|~~x98|~~x99&(x100|~~x101&~~x102)&~x103&x104&x105&x106)|(x107|x108)|~~x109&x110|~~x111|~~x112&x113|~x114|~~x115)&~~x116|x117|~~x118&~~x119|~x120|x121|~x122)|~x123&x124|x125&x126|~~x127|x128&~~x129)&x130&(~x131&~~x132&~~x133&~x134&~x135&~~x136|x137&x138|x139&x140|~~x141&(~~x142&~x143)|~x144)|x145&~~x146)&(~~x147|~x148&(~x149|~x150&x151|~~x152)&~~x153|~~x154)|~x155|~~x156|~~x157)|x158&~~x159|~x160&~x161&(~~x162&~~x163&~x164|~x165|~~x166&~x167&x168|(~~x169|(~~x170|x171|~x172|(x173&~~x174)&(x17
...
Çıxış verilənləri #1
945294826
Mənbə Japan Alumni Group Winter Contest 2012