Uolevi is constructing a labyrinth. Actually, the labyrinth is almost complete but some cells are still missing.

Each cell in the labyrinth should be either wall (#) or floor (.). Moreover, Uolevi wants that all floors are connected, i.e., it is possible to move between any two floor cells using horizontal and vertical steps.

Some cells are still missing (?). For each missing cell, Uolevi can decide whether he builds wall or floor. How many ways are there to build the labyrinth so that all floors are connected?

Input

The first input line contains three integers n, m and k: the height and the width of the labyrinth and the number of missing cells.

After this, the input describes the labyrinth. There are n lines, each containing m characters (#, . or ?).

Output

Output the number of ways Uolevi can finish the labyrinth.

Constraints

• 1 \le n, m, k \le 10

Example

Input:

4 6 2
######
.?.?.#
.#...#
.#####

Output:

2

There are two possibilities:

######
.....#
.#...#
.#####

######
...#.#
.#...#
.#####