Furukawa Nagisa's Tree

One day, Okazaki Tomoya has bought a tree for Furukawa Nagisa's birthday. The tree is so strange that every node of the tree has a value. The value of the i-th node is v_i. Now Furukawa Nagisa and Okazaki Tomoya want to play a game on the tree.

Let (s, e) be the path from node s to node e, we can write down the sequence of the values of nodes on path (s, e), and denote this sequence as S(s, e). We define the value of the sequence G(S(s, e)) as follows. Suppose that the sequence is z₀, z₁...z_l - 1, where l is the length of the sequence. We define G(S(s, e)) = z₀ × k⁰ + z₁ × k¹ + ... + z_l - 1 × k^l - 1. If the path (s, e) satisfies , then the path (s, e) belongs to Furukawa Nagisa, otherwise it belongs to Okazaki Tomoya.

Calculating who has more paths is too easy, so they want to play something more difficult. Furukawa Nagisa thinks that if paths (p₁, p₂) and (p₂, p₃) belong to her, then path (p₁, p₃) belongs to her as well. Also, she thinks that if paths (p₁, p₂) and (p₂, p₃) belong to Okazaki Tomoya, then path (p₁, p₃) belongs to Okazaki Tomoya as well. But in fact, this conclusion isn't always right. So now Furukawa Nagisa wants to know how many triplets (p₁, p₂, p₃) are correct for the conclusion, and this is your task.