Жишээ тэстүүд

Оролт
2 2 1000000007
*/
/*
Гаралт
1
Оролт
2 2 1000000007
**
\\
Гаралт
1
Оролт
2 2 3
**
**
Гаралт
2

Тэмдэглэл

The only way for sample 1 is shown on the left picture from the statement.

The only way for sample 2 is shown on the right picture from the statement.

For the third sample, there are $5$ possibilities that are listed below:

1.

$

$

2.

$

$

3.

$

$

4.

$

$

5.

$

$

The answer is then module by $3$ so the output should be $2$.