#1340. 《瞿葩的数字游戏》T3-三角圣地

《瞿葩的数字游戏》T3-三角圣地

题目描述

数字王国的中心是由一个倒三角构成。

倒三角一共 NN 层,从上往下第 ii 层有 N−i+1N-i+1 个数字。倒三角的第 11 层必须是 1∼N1 \sim N 的全排列之一,即必须使用 1∼N1 \sim N 之间的所有数字且不能重复。从第 22 层开始以后每一层的数字都是由其左上方和右上方两个数字相加得到的。例如,下面是一个合法的倒三角形:

1   2   3   4
  3   5   7
    8   12
      20

这个倒三角形的 NN 为 44,其最后一层的数字为 2020。

数字王国称最后一层的数字为“基”,请你编程求出“基”的最大值对 1000710007 取模的结果。

输入格式

一行,一个整数 NN,表示倒三角的层数。

输出格式

一行一个整数,表示 NN 层倒三角“基”的最大值对 1000710007 取模的结果。

样例

4
24
1125
700

题目来源:洛谷 P2675