- 38

## Statement

## Goal

A sheet of paper is folded left-to-right then up-to-downThen you cut out a few shapes and unfold the sheet.

The task is to determine how many parts the sheet will break up to.

**Explanations**

Lets look at the example. It is a sheet of two pieces. One piece is one or more connected

###

#..

#.#

Unfolding works as follow:

1) Down-to-up

#.#

#..

###

###

#..

#.#

2) Right-to-left

#.##.#

..##..

######

######

..##..

#.##.#

3) Go to 1, repeat N-1 times.

In this case N=1, so after unfolding there will be 5 pieces (four in the corners and one in the center).

Note that there are always as many horizontal folds as vertical ones: the number

`N`of folds is really a number of double folds, once in each direction.

Input

**Line 1:**Single integer

`N`.

**Line 2:**Two space-separated integers

`W`and

`H`represent width and height of the folded sheet respectively.

**Next**

`H`lines:`W`characters, where

Output

**Line 1:**An integer

`M`– the number of parts.

Constraints

1 ≤

1 ≤

1 ≤

`W`,`H`≤ 1001 ≤

`N`≤ 100001 ≤

`M`≤ 2³¹Example

Input

1 3 3 ### #.. #.#

Output

5

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations