JSOI is a kingdom with highly developed technology. Recently, the emergence of "Force" technology has greatly facilitated people's lives. Minister of Energy JYY is currently evaluating a newly constructed Force network.

Description

A Force network can be viewed as an undirected graph that may contain multiple edges but no self-loops. Each edge has an attribute and a value. The attribute can be one of R, G, or B, representing the type of Force on that edge. The value is a positive integer, representing the intensity of the Force on that edge.

The core of Force technology lies in fusing three different types of Force (R, G, and B) together to produce a single, usable Force. To evaluate a Force network, JYY needs to find all "triangles" (three edges connected end-to-end) that satisfy the requirements, where each of the three edges has a different attribute (one R, one G, and one B). The energy produced by such a triangle is the product of the values of its three edges.

Now, given a Force network, JYY wants to know the total energy of this network. The total energy of the network is the sum of the energies of all such triangles that satisfy the requirements.

Input

The first line contains two integers $N$ and $M$, representing the total number of vertices and the total number of edges in the Force network, respectively.

The next $M$ lines each contain three integers $u_i, v_i, w_i$ and a character $c_i$, representing an edge between vertices $u_i$ and $v_i$ with attribute $c_i$ and value $w_i$.

Output

Output a single integer representing the total energy of this Force network modulo $10^9 + 7$.

Constraints

• For 30% of the data, $N \le 100$.
• For another 30% of the data, $M \le 50,000$.
• For 100% of the data, $N \le 50,000$, $M \le 100,000$, $1 \le w_i \le 10^6$.

Examples

Input 1

4 6
1 2 2 R
2 4 3 G
4 3 5 R
3 1 7 G
1 4 11 B
2 3 13 B

Output 1

828