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

Оролт
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$.