PIPI在研究一种神秘的古代通信网络。这个网络由n个节点(编号为1,2,...,n)和m条通信线路组成。每条通信线路连接两个节点,使得它们之间可以进行数据传输。一对节点之间可能存在多条通信线路。
据研究,这个通信网络具有以下两个特性:
-
对于任何一条通信线路,连接的两个节点u和v满足1 ≤ |u - v| ≤ k。
-
每个节点恰好与偶数条通信线路相连(0也被认为是偶数)。
PIPI想知道,满足上述条件的通信网络有多少种不同的构建方式。两种构建方式不同当且仅当存在一对节点,它们之间的通信线路数量不同。
请计算满足条件的通信网络的方案数,并对10^9+7取模。