A very friendly group#1902
In a class, there are girls and boys. The class teacher, Tetyana Borysivna, needs to select a group consisting of girls and boys for a class presentation. This group must be very friendly, meaning that each selected boy must be friends with each selected girl. Tetyana Borysivna wants to know all the possible ways to form such a friendly group, so she can choose the best one from her perspective. Your task is to help her by calculating the total number of ways to form this very friendly group of children. Since the result can be very large, provide the answer modulo .
The first line of the input file contains the natural numbers , , , . Here, L \leq N \leq 100000 and K \leq M \leq 15. The next lines each contain characters, either or . The -th character of the -th line is if and only if the -th girl is friends with the -th boy.
Output the solution to the problem on a single line of the output file.
Example 1