题目描述：

为筹备校园文化晚会，学生会需要编排 M 个节目（1≤M≤10^5）。学生会有 N 个可用的节目素材 （1≤N≤5000），每个素材都有两个属性： 时长：以 “分钟” 为单位（记为 ti，1≤ti ≤K），表示该素材的播放时长； 主题类别：记为 gi（1≤gi ≤N），同一主题类别的素材风格统一，可用于满足 “风格统一” 的要求。 晚会有两个关键要求： 每个节目必须恰好持续 K 分钟（1≤K≤5000），可由若干个素材组合而成（素材顺序不影响，仅需总时 长为 K）； 节目需遵循指定的 “风格模式”：最后 M 行输入的每个大写字母代表一个风格标记（如 A、B），所有标 记相同的节目，必须使用同一主题类别的素材结尾（不同标记的节目可使用同一主题类别）。 请计算学生会共有多少种符合要求的节目编排方案。由于方案数可能极大，结果需对 1000000007 取余。

输入格式：

输入第一行包含三个整数 N（素材总数）、M（节目总数）、K（每个节目的目标时长，单位：分钟）。 接下来 N 行，每行包含两个整数 ti（素材 i 的时长）和 gi（素材 i 的主题类别）。 最后 M 行，每行包含一个大写字母 si（节目 j 的风格标记），表示所有标记为 si 的节目需使用同 一主题类别的素材结尾。

输出格式：

输出符合要求的节目编排方案总数，结果对 1,000,000,007 取余。

样例：

3 3 10
3 1
4 1
3 2
A
B
A

960

提示