Seats
TopCoder SRM 483
Time Limit: 0.1s, 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 начина в четвъртата.
Мрън!