TJU 2871. Magic Bean

天之骄灵

http://acm.tju.edu.cn/toj/showp2871.html
2871. Magic Bean
--------------------------------------------------------------------------------
Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 15 Accepted Runs: 6
--------------------------------------------------------------------------------

The Reactivity Of Bean Association (ROBA) are making research on a special kind of bean. They draw a graph, and put a bean on node No.1. Then at each unit time, the bean will jump to an adjacent node or stay still. What's more, the bean may explode and disappear at some time.
Now the researchers want to know, given the graph and the time, how many different kinds of behavior will come up. For the answer may be very large, they only want to know the result % 2007.
Please note that the bean is always at Node 1 initially.
Input
The first line of each test case contains two integers N, M, (1 ≤ N ≤ 20, 0 ≤ M ≤ 100) indicating the number of nodes and edges in the graph. Then each of the following M lines contains two integers A and B (A ≠ B, 1 ≤ A,B ≤ N), indicating node A and node B are adjacent in the graph. You can assume all the (A, B) pairs in the input are different. The last line of each test case contains the observation time T (1 ≤ T ≤ 10^6).
The input are terminated by N = M = 0.
Output
Output the number of different ways mod 2007.
Sample Input
3 2
1 2
2 3
2
0 0
Sampl