OI题库

奶牛们正在用她们笨拙的方式玩着一个版本的“快艇”游戏（一种掷骰子游戏）。她们掷N(1<=N<=20)个骰子，每个骰子有S(1& lt;=S<=8)个面。她们对一次掷骰子能达到一个特定规则（比如“包含三个2面朝上的”或者“包含一个2面朝上的和两个3面朝上的）的结果数非 常感兴趣。

帮助她们了解这个概率。写一个程序，读入N，S，并且同时读入一些描述她们的规则的表达式。计算在所有可能的掷骰子情况（3个两面的骰子 掷出的所有情况为：{1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2}）中能够满足给定规则的结果数。

基本形式表达”想要至少W个R面朝上的骰子“，它看起来像

WxR

其中0<=W<=N , 1<=R<=S。每一个测试点会给出E个表达式(1<=E<=20)，每一个表达式包含1到10个用‘+’连接的基本表达形式 (WxR)，‘+’表示“且”的关系（看下面）。每行给出的表达式之间的关系为“或”。所以下面的表达式意为“至少三个5面朝上 或 至少一个3面和两个4面”：

3x5
1x3+2x4

这里有一些4个5面骰子的掷出的结果，它们都满足上面给出的表达式：5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3; 3,4,4,5; 4,4,5,3。

编程注意：确认你可以从一行读入两个整数，然后在下一行读入一个字符串。在一些语言的输入/输出机制中，这是很难做到的。

同样注意在测试点中，掷骰子的结果数不会超过1,512,768。

输入

• 第一行：3个用空格分隔的整数：N,S,E
• 第二..E+1行：第i+1行描述了第i个像上面的表达式。

输出

• 第一行：单独的整数，表示满足给出表达式的掷骰子的结果数。

样例输入

4 5 2
3x5
1x3+2x4

样例输出

63

输入细节：这是问题描述中所用到的一个规则

输出细节：63个结果符合上述表达式