加里敦星球的人们特别喜欢喝可乐。因而， 他们的敌对星球研发了一个可乐机器人，并且放在了加里敦星球的1号城市上。
这个可乐机器人有三种行为：停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。
现在给加里敦星球城市图，在第0秒时可乐机器人在1号城市，请问经过t秒，可乐机器人的行为方案数是多少？
第1行输入两个正整数N,M。N表示城市个数，M表示道路数。
接下来M行每行2个整数u，v,表示u,v之间有一条道路。保证两座城市之间只有1条路相连，且没有任何一条道路连接两个相同城市。
最后一行是一个整数t,表示经过的时间。
输出可乐机器人的行为方案数。
3 2 1 2 2 3 2
8
样例1解释：
1->爆炸
1->1->爆炸
1->2->爆炸
1->1->1
1->1->2
1->2->1
1->2->2
1->2->3
总共8种不同的方案