Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

M. United in Stormwind
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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?

Input

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

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

Examples
Input
2 2 1
AA
BB
Output
3
Input
2 2 1
AA
AB
Output
2