소들의 야찌

소들이 주사위 게임인 야찌(Yahtzee)의 한 변형을 하고 있다. 소들은 각각 면이 $S$개($1$부터 $S$까지 번호가 매겨져 있음)인 주사위 $N$개를 굴린다. 소들은 가능한 모든 굴림 중에서 주어진 조건(예를 들어 "2가 세 개 있다" 또는 "2가 하나, 3이 둘 있다")을 만족하는 굴림이 몇 가지인지 알고 싶어 한다.

하나의 굴림은 주사위 $N$개의 결과를 순서대로 나열한 것이다. 예를 들어 면이 두 개인 주사위 세 개로 가능한 모든 굴림은 다음과 같다.

{1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2}.

각 조건은 "결과 $R$이 최소 $W$개 있기를 원한다"를 뜻하는 기본형으로 이루어지며, 다음과 같이 표기한다.

WxR

여기서 $0 \le W \le N$, $1 \le R \le S$이다.

$E$개의 식이 주어진다. 각 식은 $1$개에서 $10$개의 기본형을 +로 이은 것이며, +는 "그리고"를 뜻한다. 즉 어떤 굴림이 그 식을 만족하려면 식에 포함된 모든 기본형을 만족해야 한다. $E$개의 식은 포함적 또는(or)으로 묶인다. 즉 굴림이 식들 중 적어도 하나를 만족하면 세어 준다.

예를 들어 다음 두 식

3x5
1x3+2x4

은 "5가 최소 세 개 있거나, 또는 (3이 최소 하나 있고 4가 최소 둘 있음)"을 뜻한다. 면이 다섯 개인 주사위 네 개의 굴림 중 이 식을 만족하는 예로는 5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3 등이 있다.

$S^N$가지의 가능한 굴림 중 식을 적어도 하나 만족하는 굴림이 몇 가지인지 세어라.

제약: $1 \le N \le 20$, $1 \le S \le 8$, $1 \le E \le 20$이고, 각 식은 $1$개에서 $10$개의 기본형을 가지며, $0 \le W \le N$, $1 \le R \le S$이다. 주사위 조합의 총 개수($S^N$)는 1,512,768을 넘지 않는다.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $S$, $E$.
• 둘째 줄부터 $E+1$째 줄까지: $i+1$째 줄에는 위 형식으로 표현된 $i$번째 식이 주어진다.

• 정수 하나: $S^N$가지 조합 전체 중 식을 적어도 하나 만족하는 굴림의 개수.