## Baltic OI '17 P5 - Plus Minus

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Baltic Olympiad in Informatics: 2017 Day 2, Problem 2

Matthew the physicist studies the quantum electro-dynamics of a silicon-based rectangular microchip. The microchip consists of a very large grid of electrons. Each electron has either positive (up) or negative (down) spin, denoted by + and - respectively.

Matthew does not know the spin of all the electrons, but he has done measurements. In the th measurement, he discovered that the electron at position has a given spin . He also knows that in each subgrid, there are equally many electrons with positive and negative spin. He wants to know whether he can recover the state of every electron based on his measurements. If not, he would like to know how many possible states are consistent with his measurements. For classified reasons, he wants the answer modulo .

#### Input Specification

The first line contain three numbers , and : the height of the grid, the width of the grid and the number of measurements. The next lines contain a spin where is either + or -, and two numbers and – the coordinates of the electron. Matthew never did two measurements at the exact same location.

#### Constraints

We always have and . For subcases, the inputs have these further restrictions:

• Group 1: 12 points
• Group 2: 42 points
• Group 3: 46 points No further restrictions.

#### Output Specification

Output the total number of valid states consistent with Matthew's measurements modulo .

#### Sample Input 1

2 4 4
+ 1 1
- 1 2
+ 1 3
- 1 4

#### Sample Output 1

2

#### Explanation for Sample Output 1

The only two valid grids are

+-+-
+-+-

and

+-+-
-+-+

#### Sample Input 2

3 3 3
- 2 1
+ 2 3
+ 3 3

#### Sample Output 2

0