#P1415. 就喜欢偷家

就喜欢偷家

就喜欢偷家

题目背景

总所周知,Honor of Kings(王者荣耀)是一款非常公平的5V5Moba手游。而最近新出的一个新英雄颇受玩家的亲睐,他就是海诺,被称为新一代的对抗路霸主,这就使得使用其他英雄前往对抗路时压力倍增。某位玩家平时很少玩对抗路,一旦队友把对抗路的重担交到他的身上时,他就只喜欢使用芈月专心带线、疯狂刷野,最终带线偷家赢得胜利。

1706015538952.png

题目描述

现在你就是那位玩家。游戏开始后,你需要从左下角的水晶出发,前往右上角的敌方水晶,最终偷家成功。当然,敌人并不会眼睁睁地看着你带线从下路偷摸杀到水晶,所以你作为经常偷家的老六,必须提前规划好所有可能抵达地方水晶的路线,以防对面一起来围剿你。同时,作为一位合格的对抗路,你不会从发育路以及上方野区经过,因为你知道那样会妨碍打野和射手的发育,也会拖慢你偷家的进度。不过你可以把我方以及敌方的下半野区统统作为你发育的地区

假设王者峡谷是一个n*n的矩阵,游戏开始前将会告诉你n的大小。当然了,偷家这种事,要么一举成功,要么被抓致死,所以为了最快地偷到家,你不能回头,也就是说,你只能向上或者是向右走。你需要迅速计算出所有的可能路径,使用芈月带线偷家,带领队友走向突如其来的胜利

输入描述

输入一个整数n表示王者峡谷的边长。

输出描述

输出一行,即可能的路径总数目,答案对10^9+7取模。

输入输出样例

示例

| 输入:4

| 输出:14

示例解释:

这是n=4时所有的可能路径。

image-20231221092052458 - 副本.png

数据规模与约定

对于30%的数据,0\leqn$\leq$10;

对于60%的数据,0\leqn$\leq$10^3;

对于100%的数据,0\leqn$\leq$10^6;