P4892 GodFly’s Treasure Hunt Journey.

“Reeds and rushes grow so lush, the white dew turns to frost. The one I long for is on the other side of the water…” With a $burning$ $desire$, $GodFly$ began his journey to chase after a junior girl.

We abstract the campus as an undirected connected graph with $n$ vertices, numbered $1,2,3,...,n$. Let the vertices that $GodFly$ passes through be represented as a path set $A=\left\{a_1,a_2,a_3,...,a_m\right\}$, meaning that he passes through vertices numbered $a_1$, $a_2$, …, $a_m$ in order. Since the elements of a set are distinct, this means that $GodFly$ cannot pass through the same vertex repeatedly. Now $GodFly$ wants to walk from vertex $1$ to vertex $n$, but his leg problem causes him a lot of trouble. Define that $GodFly$ has passed through $m$ vertices, is currently at vertex $a_m$, and the path set is $A=\left\{a_1,a_2,a_3...,a_{m-1}\right\}$ (before adding the new vertex $a_m$). Then his total stamina cost is $w_m=(w_{m-1}+a_m*sum(A))$%$2$, where $w_{m-1}$ is the stamina cost of the previous path set. For the set $A$, $sum(A)=a_1+a_2+...+a_{m-1}$. When $w=0$, we say $GodFly$ is in the “滑基态” ("huaji state"). Otherwise, when $w=1$, we say $GodFly$ is in the “对偶态” ("dual state"). Now $GodFly$ wants to know the number of ways such that after he reaches vertex $n$, he is in the huaji state or the dual state. Since this number may be very large, you only need to output the result modulo $19260817$. Note that two ways are considered different if and only if they have at least one edge traversed differently, rather than having different path sets.

The first line contains two integers $n$ and $k$, representing the number of vertices and the number of edges. The next $k$ lines each contain two integers $u$ and $v$, indicating that there is an edge between vertex $u$ and vertex $v$. The last line of the input contains an integer $c$. $c=0$ means you need the number of ways for the huaji state, and $c=1$ means you need the number of ways for the dual state.

One line containing one integer, the number of ways, as described in the statement.

**Constraints** For $30$% of the testdata, $n