高桥和青木想要一起造一个数列。

首先，高桥会造出一个满足以下条件的数列$a$：

• $a$的长度为$N$。
• $a$中的所有元素都是一个$[1,K]$内的整数。
• $a$是一个回文串。

然后，青木会进行任意多次以下的操作：

• 把$a$中的第一个元素移到最后。

经过这些步骤，一共可以得到多少种不同的数列$a$呢？答案对1e9+7取模。