Background

“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.

Problem Description

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.

Input Format

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.

Output Format

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

3 3
1 2
2 3
1 3
1

2

10 30
6 3
5 3
6 7
10 9
2 8
7 2
10 6
7 1
9 4
3 9
7 1
2 2
10 6
7 7
2 4
6 8
1 1
6 4
3 9
8 7
6 2
7 2
1 4
5 4
8 6
2 4
7 1
4 2
10 9
1 6
0

1094

Hint

Constraints

For $30$% of the testdata, $n<=10$, $k<=45$, with no multiple edges or self-loops.

For $60$% of the testdata, $n<=15$, $k<=300$.

For $80$% of the testdata, $n<=15$, $k<=100000$.

For $100$% of the testdata, $n<=18$, $k<=100000$.

Sample Explanation

As shown in the figure, initially at vertex $1$, the path set is $\left\{1\right\}$, and the cost is $0$.

If you go from vertex $1$ to vertex $2$ and then to vertex $3$: when arriving at vertex $2$, the cost is $(0+2*sum(\left\{1\right\}))$%$2=2*1$%$2=0$, and then add $2$ into the path set, so the path set becomes $\left\{1,2\right\}$. When arriving at vertex $3$, since the previous cost is $0$, the cost is $(0+3*sum(\left\{1,2\right\}))$%$2=3*(1+2)$%$2=1$.

If you go directly from vertex $1$ to vertex $3$, then the cost is $(0+3*sum(\left\{1\right\}))$%$2=3*1$%$2=1$.

Therefore, the number of ways that end at vertex $3$ with cost $1$ is $2$.

Hint

The time limit for this problem is $3s$, and you may enable $O_2$ optimization, so you do not need to worry too much about constant factors. However, please make sure your algorithm is efficient enough.

Translated by ChatGPT 5