Seats
TopCoder SRM 483
Time Limit: 0.2s, Memory Limit: 64MiB
Бродейки из мола, Ели и нейните приятелки решиха да влязат в киното. Бидейки кифли, просто да гледат филма би било скучно. Затова те са решили да седнат или на един и същи ред, или на една и съща колона, като така могат да си приказват и лигавят по време на филма. Това, че може да има хора между тях не е проблем, стига да е изпълнено условието всички да са на един и същи ред или в една и съща колона.
По даден план на вече заетите седалки, определете по колко начина могат да седнат момичетата.
По даден план на вече заетите седалки, определете по колко начина могат да седнат момичетата.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – от колко човека (заедно с Ели) се състои компанията. На втория ред са зададени две цели числа H и W – съответно колко реда и колко колони от седалки има. Следват H реда, всеки съдържащ по W символа: '#' ако съответната седалка е вече заета, или '.' в противен случай.
Изход
На единствен ред на стандартния изход изведете едно цяло число – по колко начина могат да седнат момичетата, взимайки предвид позицията им една спрямо друга. Тоест считаме за различни две разположения, дори ако момичетата заемат едни и същи седалки, но в едното, например, Крис се намира от лявата страна на Ели, а в другото – от дясната.
Ограничения
- 1 ≤ N ≤ 8
- 1 ≤ H, W ≤ 50
Примерен Вход | Примерен Изход |
---|---|
2 3 4 .#.. .##. .... | 34 |
Момичетата могат да седнат по 6 начина в първия ред, по 2 начина във втория и по 12 начина в третия. Ако решат да са в една и съща колона, то те могат да са по 6 начина в първата, по нула начина във втората (има само една празна седалка), по 2 начина в третата и по 6 начина в четвъртата.