Problem H
Hopping Haven

Oh no! The Harrowfall Horde has, once more, decided to launch their magic squares against us. And again, they’ve sealed us within a great rectangular wall!

While it won’t hurt our people – magic squares never do – every hit will hurt our economy. They’ll manage to damage houses or crops, and that is really annoying. Fortunately, a magic square will only deal damage the first time it hits the kingdom: Subsequent hits from the same square do no damage.

Since we captured some magic squares last time, we’ve managed to uncover their secrets. After magic square $i$ appears, it teleports $\Delta x_{i}$ units horizontally and $\Delta y_{i}$ units vertically on every odd-numbered second. Also, instead of colliding with each other, it seems like multiple magic squares are able to occupy the same tile. And when a magic square moves beyond the boundaries of the great rectangular wall, it vanishes. Thanks to our spies, we also know when and where magic square $i$ will appear: It seems to always be somewhere on top of the great rectangular wall.

This by itself won’t help us much: After all, our rectangular kingdom is immovable…or is it? Thanks to the tireless efforts by the Institute of Dimensional Invocation (IDI), we have successfully reverse-engineered the magic behind the squares. At last, our kingdom has legs!

On positive even-numbered seconds, we can either remain in place or shift exactly one unit in either a horizontal or vertical direction, though never both at once. While the kingdom can now move, it cannot be placed on top of water nor the great wall – unlike the magic squares, which can.

Given this information, you, the shell-script shaman, have been tasked with determining how many magic squares can be avoided. But the king isn’t just interested in the number of magic squares the kingdom can avoid – he also wants to know the number of distinct movement sequences that achieve this. According to him, reporting this to the Hopping Haven will severely damage their morale.

Input

The first line of the input contains the integers $W$, $H$ and $N$, the width and height of the map, as well as the number of magic squares.

Then follow $H$ lines, each with exactly $W$ characters each, representing the map. The map will only contain the following characters:

• ‘.’, representing land

• ‘~’, representing water

• ‘#’, representing a piece of the great rectangular wall

• ‘x’, representing a piece of our rectangular kingdom

Finally, $N$ lines follow, each representing a single magic square. Each line contains $5$ integers, $t_i$, $x_i$, $y_i$, $\Delta x_i$, $\Delta y_i$, denoting the time $t_i$ the magic square appears at $\langle x_i, y_i\rangle $, teleporting $\langle \Delta x_i, \Delta y_i\rangle $ units every odd-numbered second.

Rows are indexed from the top, so the first row is $y = 0$, the second is $y = 1$, and so on.

Output

Output the number of magic squares the kingdom can evade and the number of distinct move sequences that achieve this, assuming time starts at second 0. As the number of move sequences may be very large, output both numbers modulo $1\, 000\, 000\, 007$.

The move sequence ends at the latest time at which any magic square vanishes.

Limits

• $3 \leq W, H \leq 50$

• $0 < N < 100$

• There is at most $6$ active magic squares at any given time

• The border of the map will only contain ‘#’ characters, and ‘#’ characters will only appear there

• All ‘x’ characters on the map form a rectangle

• $0 \leq t_i < 200$, and $t_i$ is always an even number

• $\langle x_i, y_i\rangle $ is always on the border of the map

• $|\Delta x_i| < W$ and $|\Delta y_i| < H$

• $0 < |\Delta x_i| + |\Delta y_i|$

5 5 1
#####
#..~#
#xx.#
#xx.#
#####
0 1 0 0 1

1 2

5 5 2
#####
#..~#
#xx.#
#xx.#
#####
2 1 0 0 1
10 3 4 0 -1

2 48

5 5 3
#####
#...#
#...#
#xx.#
#####
10 0 0 1 0
14 2 0 0 1
14 2 4 0 -1

1 627232