프리픽스 프리 코드

소문자로 이루어진 $n$개의 초기 문자열이 있고, 어떤 초기 문자열도 다른 초기 문자열의 접두사가 아니다. 이제 이 중 $k$개를 중복 없이 골라 이어 붙인다고 하자. 이렇게 만들 수 있는 합성 문자열의 개수는 다음과 같다.

$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$

이 과정으로 만들 수 있는 모든 합성 문자열을 사전순으로 정렬했을 때, 그 목록에 속함이 보장된 시험 합성 문자열이 주어진다. 이 시험 합성 문자열이 정렬된 목록에서 몇 번째인지 $10^9 + 7$로 나눈 나머지를 구하라. 목록의 첫 번째 합성 문자열은 1번이다.

입력은 하나의 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $k$가 순서대로 주어진다 ($1 \le k \le n$). $n$은 초기 문자열의 개수이고, $k$는 합성 문자열을 만들 때 고르는 초기 문자열의 개수이다. $n$과 $k$의 상한은 아래 문단에 나오는 문자열의 제약에 따라 정해진다.

다음 $n$개 줄에는 각각 하나의 문자열이 주어진다. 이 문자열은 하나 이상의 소문자 a..z로 이루어지며, $n$개의 초기 문자열이다. 어떤 초기 문자열도 다른 초기 문자열의 접두사가 아님은 보장된다.

마지막 줄에는 소문자 a..z로만 이루어진 또 다른 문자열이 하나 주어진다. 이것이 시험 합성 문자열이며, 정렬된 목록에서의 위치를 구해야 한다. 이 시험 합성 문자열은 서로 다른 $k$개의 초기 문자열을 이어 붙인 것임이 보장된다.

시험 문자열을 포함해 입력으로 주어지는 모든 문자열의 길이 합은 $10^6$자를 넘지 않는다.

정렬된 합성 문자열 목록에서 시험 합성 문자열이 위치하는 번호를 하나의 정수로 출력한다. 이 수를 $10^9 + 7$로 나눈 나머지를 출력하라.