终于，小明毕业了，他规划进行一次毕业旅行。经过长时间的筛选，小明最终定下来 n 个城市作为旅行的目的地，并将这些城市人为编号为 1,2,.......,n。这些城市由 m 条双向道路连接而成。
小明非常喜欢其中编号为 1,2,.......,k 的那些城市，在他的旅行中，必须经过 [1,k] 这 k 个城市至少一次。当 k 为 0 时，表示小明不是必须要经过规定的城市。
现在小明会进行为期 d 天的旅行，每一天小明都可以前往一个城市。小明的起点可以是 1\sim n 中任意一个城市，终点也可以是 1\sim n 中的任意一个城市，他每天都可以从一个城市走到另一个有道路直接相连的城市。我们可以将小明的旅行表示成一个长度为 d 的数列，其中数列的第 i 项为小明第 i 天所在的城市（第 1 项作为起点城市）。
注意：小明不能连续两天呆在一个城市，即每一天小明必须前往一个有边相连的其他城市。
例如，假设一定要去到 1,2 这两个城市，旅行 3 天，那么旅行数列 {1,2,1} 是一种合法的方案, 而 {1,2,2} 是不合法的，这种方案中小明第 2 天到第 3 天都在城市 2。
现在小明想知道有多少种不同的旅行方案，即可以表示成多少个长度为 d 的不同数列，只要有某一天所在的城市不同，就认为这两种方案不同。
小明又将这个问题交给了精通编程的你，现在想知道方案书模 10^9+9 的答案。