There are N boys and M girls in a dance school. The teachers are organizing a performance and they need exactly **K** boy-girl couples for their show. Unfortunately, this is not a straightforward task since some children cannot be paired with each other (due to differences in height, skill, etc.). One of the teachers is a computer science graduate, and has decided to count the number of ways to select **K** couples.
You are given a String[] **canDance** containing exactly N elements, each with exactly M characters. The j-th character of the i-th element of **canDance** is 'Y' if boy i can be paired with girl j, and 'N' otherwise. Return the number of distinct valid ways to select exactly **K** boy-girl pairs. |