题目内容

服务网格里有 $k$ 个节点和 $e$ 条有向链路。每条链路带一个正整数时延，以及标签字符，只能是 $A$、$B$、$C$ 之一。

流量从节点 $beg$ 出发，沿链路走到节点 $fin$。把途经链路的标签按经过顺序拼起来，得到这条路由的标签串。

给定非空禁用串 $F$。若某条路由的标签串里不出现连续子串 $F$，则称该路由合规。

节点与链路都可以重复经过；每走一条链路都要累加其时延。需要求出合规路由的最小总时延，以及达到该时延的不同路由条数。条数对 $1000000007$ 取模。

链路按输入顺序编号。两条路由只要经过的链路编号序列不同，就算不同路由；即便端点、时延和标签都一样，编号不同的链路也分开计数。

当 $beg = fin$ 时，允许一条不走任何链路的空路由：时延为 $0$，标签串为空。

输入描述

第一行两个整数 $beg,fin$，用逗号分隔，表示起点与终点（$1\le beg,fin\le k$）。

第二行两个整数 $k,e$（$1\le k\le 5000$，$0\le e\le 20000$），用空格分隔，表示节点数与链路数。

第三行给出禁用串 $F$（$1\le |F|\le 50$，仅含 $A$、$B$、$C$）。

随后 $e$ 行，每行四个字段 $u,v,w,ch$，用逗号分隔，表示一条从 $u$ 到 $v$、时延为 $w$、标签为 $ch$ 的链路。其中 $1\le u,v\le k$，$1\le w\le 10^9$，且 $ch\in\{A,B,C\}$。

同一对端点之间可以有多条链路，也允许指向自身的链路。

输出描述

输出两行：第一行是最小总时延，第二行是最优路由条数对 $1000000007$ 取模的结果。

若不存在合规路由，则第一行输出 $-1$，第二行输出 $0$。

补充说明

两成测例满足：$k\le 10$，$e\le 20$，$|F|\le 4$，并且每条链路的起点编号都小于终点编号。

另有三成测例里，禁用串 $F$ 恰好只有一个字母。

其余一半测例不做上述收紧。

样例1

输入

1,4
4 5
BA
1,2,2,B
2,4,2,A
1,3,3,A
3,4,3,B
1,4,6,C

输出

6
2

说明

路由 $1\to 2\to 4$ 时延为 $4$，但标签串恰为禁用串 $BA$，不合规。

路由 $1\to 3\to 4$ 的标签串为 $AB$，以及直达 $1\to 4$ 的标签串 $C$，二者均合规，时延都是 $6$。

样例2

输入

2,2
3 1
ABC
1,2,5,A

输出

0
1

说明

起点与终点相同，空路由合法，时延 $0$，计 $1$ 条。