Biljana's Word Puzzle

Biljana loves word puzzles. In her game, two words are called similar if one can be obtained by reordering the letters of the other. She now has n words, and she wants to select a subset of these words such that there are exactly k pairs of similar words among the chosen ones.

More formally, let the selected set of words be S. For every pair of distinct words (i, j) in S, if word i can be rearranged to obtain word j (i.e. they are anagrams), then they form a similar pair. Count the number of ways to choose S so that the total number of similar pairs is exactly \(k\). Since the answer can be very large, output it modulo \(10^9+7\).

Note:

• Two words are similar if their sorted characters are equal, i.e. if \(\text{sort}(s_i)=\text{sort}(s_j)\).
• A subset can be empty or can contain any number of words.

inputFormat

The first line contains two integers \(n\) and \(k\) (where \(1 \leq n \leq 10^5\) and \(0 \leq k\leq \text{some bound}\)) — the number of words and the required number of similar pairs.

Each of the following \(n\) lines contains one word consisting of lowercase English letters.

outputFormat

Output a single integer, the number of valid ways to choose a subset of words such that the number of similar pairs is exactly \(k\), modulo \(10^9+7\).

sample

3 1
abc
acb
def

2