바이러스
시간 제한2초메모리 제한256 MB
길이 n의 소문자 문자열 중 모든 위치가 주어진 m개의 바이러스 패턴 중 하나와 일치하는 부분 문자열 안에 들어가는 문자열의 개수를 1e9+7로 나눈 나머지를 구한다.
문제
어떤 백신 회사에서 바이러스를 연구한다. 이들은 m가지 종류의 바이러스가 존재함을 알고 있다. 각 바이러스는 라틴 알파벳 소문자로 이루어진 문자열로 주어진다. 서로 다른 종류의 바이러스에는 서로 다른 문자열이 대응된다.
최근에는 이전에 연구되지 않았던 대상인 완전 감염 문자열에 대한 연구가 시작되었다. 문자열 s가 완전 감염 문자열이라는 것은, s의 모든 문자에 대해 그 문자를 포함하고 바이러스인 s의 부분 문자열이 존재한다는 뜻이다.
주어진 바이러스에 대해 길이 n인 완전 감염 문자열의 개수를 구해야 한다. 이 수는 매우 클 수 있으므로 109+7로 나눈 나머지를 출력한다.
입력
첫 번째 줄에 두 정수 n과 m이 주어진다. (1 ≤ n ≤ 400; 1 ≤ m ≤ 20)
다음 m개의 줄에 바이러스의 설명이 주어진다. 각 줄에는 라틴 알파벳 소문자로 이루어진 문자열이 주어진다.
각 바이러스의 길이는 양수이고 20자를 넘지 않는다.
출력
완전 감염 문자열의 개수를 109+7로 나눈 나머지를 한 줄에 출력한다.