菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数k，要求菲波那契数列中第k个数是多少。
输入一行，包含一个正整数k。（1 ≤ k ≤ 46）
输出一行，包含一个正整数，表示菲波那契数列中第k个数的大小。
19
4181
神奇的斐波那契数列
故事得从西元1202年说起，话说有一位意大利青年，名叫斐波那契。在他的一部著作中提出了一个有趣的问题：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子?
斐波那契，又称比萨的列奥纳多（英语：Leonardo Pisano Bigollo，或称Leonardo of Pisa, Leonardo Pisano, Leonardo Bonacci, Leonardo Fibonacci，1175年－1250年[1]），出生于意大利的比萨，意大利数学家，西方第一个研究斐波那契数，并将现代书写数和乘数的位值表示法系统引入欧洲。
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……