余神有一张n 个点、m 条边的有向无权图,所有点从1 到n 标号。
现在余神 想知道有多少种添加有向边的方案(可不添加),使得该图满足下列条件:
1、从点i 出发,可以到达点i+1,i+2,…..,n。
2、任意从u 到v 的有向边满足不等式:u<v。
3、两点之间最多有一条边。
4、对于一对点i、j(i<j),若j-i<=k,那么从i 到j 的最短距离等于j-i。
5、对于一对点i、j(i<j),若j-i>k,那么从i 到j 的最短距离等于j-i 或j-i-k。
我们认为两种添加边的方案不同,当且仅当存在至少一对点i、j(i<j),一张图中有一条从i 连向j 的边,而另一张图中没有。
帮助余神!
由于要求的答案可能太大,将答案对1000000007 取模后输出。