GodFly's Campus Journey

In this problem, the campus is modeled as an undirected connected graph with (n) nodes labeled (1,2,\dots,n). GodFly wants to travel from node (1) to node (n) along a simple path (i.e. no node is visited more than once). Let the nodes GodFly visits in order be (A = {a_1, a_2, \dots, a_m}) where, by convention, the starting node is (a_1 = 1) and the destination is (a_m = n). Note that when moving to a new node (a_m), the cost incurred depends on the set (A = {a_1,a_2,\dots,a_{m-1}}) of nodes visited before the new node. Specifically, if the current overall energy cost is (w_{m-1}) and (\text{sum}(A) = a_1+a_2+\dots+a_{m-1}), then upon visiting (a_m) the new overall cost is computed as: [ w_m = \Bigl(w_{m-1} + a_m \times \text{sum}(A)\Bigr) \bmod 2. ] We define the two states of GodFly as follows:

• If (w = 0) the state is called "sliding state".
• If (w = 1) the state is called "dual state".

Initially, GodFly starts at node (1) with (w = 0). (Note that no energy cost is incurred for the starting node since there are no previously visited nodes.)

Your task is to count the number of simple paths from node (1) to node (n) that result in each final state (sliding and dual). Two paths are considered different if and only if there is at least one edge that is used in one path but not in the other. Since the numbers can be huge, output the results modulo (19260817).

Note: All formulas are in (\LaTeX) format.

inputFormat

The input begins with a line containing two integers (n) and (m), representing the number of nodes and edges respectively. Each of the next (m) lines contains two integers (u) and (v) indicating there is an undirected edge between nodes (u) and (v). It is guaranteed that the graph is connected, has no self-loops and no multiple edges. Nodes are numbered from (1) to (n).

outputFormat

Output two integers separated by a space. The first integer denotes the number of ways to reach node (n) in the sliding state (i.e. (w=0)), and the second denotes the number of ways to reach node (n) in the dual state (i.e. (w=1)). Both answers should be given modulo (19260817).

sample

3 2
1 2
2 3

0 1