题目描述

河流污染治理需要规划污水处理厂的运行方案。沿河$NC$个城市各自建有污水处理厂，并通过管道与相邻城市连接。每个污水处理厂有三种运行模式：

1. 自主处理(V)：处理来自上游或下游的污水（若有）并排放净水至河流
2. 向右传输(>)：将自身及下游污水输送至上游处理厂（需确保上游厂未向左传输）
3. 向左传输(<)：将自身及上游污水输送至下游处理厂（需确保下游厂未向右传输）

要求：

• 所有污水必须被处理
• 至少有一个处理厂处于自主处理模式

输入格式

多组测试数据，每组一个整数$NC$表示城市数量（$1 \leq NC \leq 100$）

输出格式

每组数据输出可能的运行方案总数$NS$

样例输入

2
3
20

样例输出

3
8
102334155

方案示例

• 2个城市：VV、>V、V< 共3种
• 3个城市：VVV、V<V、VV<、V><、>VV、>V<、>>V、<VV 共8种

题目来源

2002年西南欧地区竞赛