#P1324. 计算魔法序列的第n项

计算魔法序列的第n项

题目描述

在古老的魔法书中记载着一个神秘的序列,这个序列被称为"魔法序列"。魔法序列的前两项都是1,从第三项开始,每一项都等于前两项之和。现在你需要编写一个程序来计算这个序列的第n项。

魔法序列的计算公式如下:

  • 当1 ≤ x ≤ 2时,魔法序列的第x项为1
  • 当x ≥ 3时,魔法序列的第x项等于第(x-1)项加上第(x-2)项

输入格式

输入一个整数n(0 < n < 40),表示要计算的魔法序列的项数。

输出格式

输出魔法序列的第n项的值。

样例

7
13

提示

请注意处理第1项和第2项的特殊情况