菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数k，要求菲波那契数列中第k个数是多少。
输入格式:
输入一行，包含一个正整数k（1<=k<=46）。
输出格式:
输出一行，包含一个正整数，表示菲波那契数列中第k个数。
样例">输入样例:
19
输出样例:
4181
用递归会超时。
k = int(input())
if k ==1 or k == 2:
print(1)
else:
a1 = a2 = 1
for i in range(k-2):
a1,a2 = a2,a1+a2
print(a2)
4181
用递归会超时。
k = int(input())
if k ==1 or k == 2:
print(1)
else:
a1 = a2 = 1
for i in range(k-2):
a1,a2 = a2,a1+a2
print(a2)
