보안종결자

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

음지에서 살아가는 보안 초전문가 슈퍼코더 K 는 이번에 새로운 은행의 전산망을 해킹하려고 합니다. 그에게는 원래 은행의 전산망을 해킹하는 것은 손바닥 뒤집는 것보다 쉬운 일인데, 2011년에 추가된 침입 감지 시스템(Intrusion Detection System, IDS) 때문에 골치를 앓고 있습니다. 이 침입 감지 시스템은 네트워크의 모든 트래픽을 감시하면서 그 중 특정 문자열을 발견하는 경우 곧장 해킹 시도가 있었음을 관리자에게 알려줍니다. 따라서 서버로 보내는 데이터에는 이 문자열이 포함되어 있으면 안 됩니다. 다행히 이 침입 감지 시스템이 인식하는 패턴들을 모두 이미 확보했습니다.

이 전산망의 루트 비밀번호는 알파벳 소문자로 구성된 길이 n 의 문자열인데, 앞에서 이야기한 IDS 의 존재 때문에 해킹 시도로 인식되는 패턴들을 포함하는 비밀번호는 입력할 수 없습니다. 길이 n 인 소문자 문자열 중 IDS 에 인식되지 않는 문자열의 개수를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 만들 문자열의 길이 N (1 <= N <= 100) 과 IDS 가 인식하는 패턴의 수 M (1 <= M <= 100) 이 주어집니다. 그 후 M 줄에 하나씩 문자열은 길이 10 이하의 알파벳 소문자 문자열로 IDS 가 인식하는 패턴이 주어집니다.

출력

각 테스트 케이스마다 IDS 에 인식되지 않는 문자열의 수를 출력합니다. 문자열의 수가 클 경우 10007 로 나눈 나머지를 출력합니다.

예제 입력

3
2 2
rm 
dd
4 4
a
b
c
d
100 4
aa
ba
ab
cd

예제 출력

674 
4095
5293 

노트

5개의 댓글이 있습니다.