Ghép ô chữ

Xem PDF

Nộp bài


Điểm: 10
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

ngochuy thích giải ô chữ. Loại ô chữ mà anh ấy thích là ô chữ kiểu đảo chữ (phép đảo chữ ở đây có nghĩa là tạo ra một từ có nghĩa bằng cách sắp xếp lại các chữ cái trong từ ban đầu, chẳng hạn \("haungu"\) là một từ được tạo ra bằng cách đảo các chữ cái của \("hanguu"\)): mỗi gợi ý là một từ được tạo ra bằng cách đảo các chữ cái của đáp án.

ngochuy có một tập hợp \(n\) từ mà anh ấy nghĩ sẽ phù hợp với câu đố tiếp theo của anh. Anh ấy muốn chọn ra một tập con của tập \(n\) từ này, sao cho có đúng \(k\) cặp từ thỏa mãn: có thể đảo các chữ cái của từ thứ nhất để tạo ra từ thứ hai. Hãy giúp ngochuy tính số tập con thỏa mãn.

Input:

Dòng đầu tiên chứa số \(n\) \((1\leq n\leq 2000)\) và \(k\) \((0\leq k\leq 2000)\) : Số từ mà ngochuy nghĩ ra và số cặp từ anh ấy yêu cầu.

Mỗi dòng trong \(n\) dòng tiếp theo chứa một từ có tối đa \(10\) kí tự, và tất cả các kí tự đều là chữ cái viết thường. Tất cả các từ đôi một phân biệt.

Output:

Số tập con thỏa mãn. Do kết quả có thể lớn, in ra kết quả modulo \(10^9 + 7\) \((1000000007)\)

SAMPLE INPUT 1:

3 1
ovo
ono
voo

SAMPLE OUTPUT 1:

2

SAMPLE INPUT 2:

5 2
trava
vatra
vrata
leo
ole

SAMPLE OUTPUT 2:

3

SAMPLE INPUT 3:

6 3
mali
lima
imal
je
sve
ej

SAMPLE OUTPUT 3:

6

Giải thích sample input 1:

  • Có \(2\) tập con có đúng một cặp từ thỏa mãn điều kiện là: {ovo, ono, voo}{ovo, voo}

Subtask:

  • \(38%\) số test có \((n\leq 15)\)
  • \(19%\) số test tiếp theo có \((k\leq 3)\)
  • \(42%\) số test còn lại không có điều kiện gì thêm

Copy nguồn dịch từ: minhcool

\[Credit: COCI 2020/2021 - Contest 6 \]