PIPI与POPO大战三天三夜，PIPI使出武林绝学“欧拉欧拉欧拉！”，而POPO以“木大木大木大！”回击，最终PIPI不幸落败。
战败的PIPI不得已得计划好自己的逃跑路线，一共有n块区域，编号为1-n，所有的区域之间均两两联通。已知PIPI逃跑的起点为1号区域，每过一天他都会前往与前一天不同的区域。
请问经过k天后，PIPI回到1号区域的逃跑路线有多少条，答案对1e9+7取模。

输入两个整数n与k（1<=n<=10^9,1<=k<=10^18）。

输出PIPI有多少条逃跑路线。

中等 数学 动态规划