时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
给一个含n个点m条边的有向无环图（允许重边，点用1到n的整数表示），每条边上有一个字符，问图上有几条路径满足路径上经过的边上的字符组成的的字符串去掉空格后以大写字母开头，句号 '.' 结尾，中间都是小写字母，小写字母可以为0个。
输入描述:
第一行两个整数n,m
接下来m行，每行两个整数a,b和一个字符c，表示一条起点为a，终点为b的边，边上的字符是c
1 ≤ n, m ≤ 50000
1 ≤ a < b ≤ n
c可以是大小写字母、句号 '.' 或空格（方便起见用 '_' 表示空格）
输出描述:
输出一个整数，表示答案对232取模的结果
示例1
输入
复制
6 11
1 2 A
1 2 _
3 4 _
2 4 B
2 3 a
2 3 _
2 4 b
4 5 .
3 5 .
2 5 .
5 6 _