408613: GYM103202 M United in Stormwind

The adventurers gather together in the majestic capital city, Stormwind, for a referendum about the future of their alliance. The referendum contains $$$m$$$ questions, and each question has two options, A and B.

After collecting the results of the referendum, the alliance received $$$n$$$ survey results. When sorting out the results, Alice comes up with a special idea. She thinks that a nonempty subset of questions is discriminative if there are at least $$$k$$$ pairs of results different in at least one of the questions in the set.

She wants to know the number of different discriminative subsets of questions. Can you help Alice solve this problem?

The first line contains three integers $$$n, m, k$$$ $$$(1 \le n \le 2 \times 10^5, 1 \le m \le 20, 1 \leq k \leq \frac{n(n-1)}{2})$$$, as specified in the problem statement.

Each of the following $$$n$$$ lines contains a string of length $$$m$$$, which contains only A and B, indicating the answer to each question in the referendum results.

Output a single integer that represents the number of different discriminative subsets of questions.

2 2 1
AA
BB

3

2 2 1
AA
AB

2