#abc235h. [abc235_h]Painting Weighted Graph
[abc235_h]Painting Weighted Graph
Problem Statement
Given is an undirected graph with vertices and edges. The -th edge connects Vertices and and has a weight of .
Initially, all vertices are painted black. You can do the following operation at most times.
- Operation: choose any vertex and any integer . Paint red all vertices reachable from the vertex by traversing edges whose weights are at most , including itself.
How many sets can be the set of vertices painted red after the operations?
Find the count modulo .
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
Sample Output 1
For example, an operation with paints Vertices red, and an operation with paints Vertex .
After at most one operation, the set of vertices painted red can be one of the following six: .
Sample Input 2
Sample Output 2
The given graph may not be connected.
Sample Input 3
Sample Output 3
The given graph may have multi-edges and self-loops.