문제
0과 1로 이뤄진 길이 N의 문자열이 있다. M개의 0과 1로 이뤄진 길이 K의 문자열 패턴이 존재하지 않는 문자열이 몇개가 있는지 찾아내는 프로그램을 작성하라.
예를 들어 N = 4이고, 나타나지 말아야 할 문자열 패턴이 { 101, 111 }이 존재할 경우 가능한 경우는 다음과 같다.
0000, 0001, 0010, 0011, 0100, 0110, 1000, 1001, 1100
불가능한 경우는 다음과 같다.
0101, 0111, 1010, 1101, 1110, 1111
입력
입력의 첫번째 줄에는 N, M, K 가 입력된다( 1≤N≤109, 1≤K≤8, 1≤M≤2k).
그 다음 줄 부터 M개의 줄에는 존재하면 안되는 문자열 패턴이 입력된다.
문자열 패턴의 길이는 정확히 K이며 0 과 1 로 이뤄진다.
출력
각 입력에 대해 가능한 경우의 수를 2010 으로 나눈 나머지를 출력한다.
예제
4 2 3
111
101
9
로그인해야 코드를 작성할 수 있어요.