Cow Yahtzee

The cows are playing a version of Yahtzee, the dice-rolling game. They roll $N$ dice, each having $S$ sides (faces numbered $1$ through $S$). They want to know, over every possible roll, how many rolls satisfy a given criterion (such as "contains three 2's" or "contains one 2 and two 3's").

A roll is an ordered sequence of the $N$ dice results. For example, the complete set of rolls for three two-sided dice is:

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

Each criterion is built from a basic form that expresses "want at least $W$ copies of result $R$", written as:

WxR

where $0 \le W \le N$ and $1 \le R \le S$.

You are given $E$ expressions. Each expression is $1$ to $10$ basic forms joined by +, where + means "and": a roll satisfies the expression only if it satisfies every one of its basic forms. The $E$ expressions are combined with an inclusive or: a roll counts if it satisfies at least one of the expressions.

For example, the two expressions

3x5
1x3+2x4

mean "at least three 5's, OR (at least one 3 and at least two 4's)". Some rolls of four five-sided dice that satisfy them are: 5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3.

Count how many of the $S^N$ possible rolls satisfy at least one expression.

Constraints: $1 \le N \le 20$, $1 \le S \le 8$, $1 \le E \le 20$, each expression has $1$ to $10$ basic forms, $0 \le W \le N$, and $1 \le R \le S$. The total number of dice combinations ($S^N$) never exceeds 1,512,768.

• Line 1: three space-separated integers $N$, $S$, and $E$.
• Lines 2 to $E+1$: line $i+1$ contains expression $i$, in the format described above.

• A single integer: the number of rolls, out of all $S^N$ combinations, that satisfy at least one expression.