F. *【动态规划：区间一维一边推】数的计数[NOIP普及组2001]

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

给出正整数 $n$ ，要求按如下方式构造数列：

请你求出，一共有多少个合法的数列。两个合法数列 $a,b$ 不同当且仅当两数列长度不同或存在一个正整数 $i \leq |a|$ ，使得 $a_i \neq b_i$ 。

【输入格式】

输入只有一行一个整数，表示 $n$ 。

【输出格式】

输出一行一个整数，表示合法的数列个数。

满足条件的数列为：

对于全部的测试点，保证 $1 \leq n \leq 10^3$ 。