CF231E Cactus

A connected undirected graph is called a vertex cactus, if each vertex of this graph belongs to at most one simple cycle. A simple cycle in a undirected graph is a sequence of distinct vertices $ v_{1},v_{2},...,v_{t} $ $ (t>2) $ , such that for any $ i $ $ (1

The first line contains two space-separated integers $ n,m $ $ (2

Print $ k $ lines: in the $ i $ -th line print a single integer — the number of distinct simple ways, starting at $ x_{i} $ and ending at $ y_{i} $ , modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).