Statement

In a magical forest far-far away lives the Miraculous Deer. It likes to take magical walks along the trails of the forest. You're wondering, how many distinct magical walks can it take? The forest contains N meadows, numbered from 1 to N. There are M trails, numbered from 1 to M. Trail i connects meadows a_i and b_i, and has a magical value c_i. A walk starts at a meadow and visits a number of meadows by traversing trails, arriving at a meadow. The walk might visit the same meadow multiple times. The length of the walk is the number of traversed trails. A walk of length k is a magical walk, if the magical values of the traversed trails in order are m_1, m_2, …, m_k, and (1) k ≥ 1, (2) m_i+1=m_i+1 for all 1 ≤ i ≤ k-1. Two magical walks are different if the sequences of traversed trails are different. Write a program that calculates the number of different magical walks modulo 10^9+7!