小蒜蒜最近学习了斐波那契数列。

斐波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和。

给出一个正整数 k，要求斐波那契数列中第 k 个数是多少。

输入格式
输入一行，包含一个正整数 k。（1≤k≤46）

输出格式
输出一行，包含一个正整数，表示斐波那契数列中的第 k 个数。

输出时每行末尾的多余空格，不影响答案正确性。

样例输入
19
样例输出
4181
大佬们，帮帮忙！寒假作业，需及时提交！好难啊！30高分悬赏！（可以用C++或Python）

我自己写了一个，大家看看吧！C++的：
include <iostream>
using namespace std;
int h[46];
int main()
{
    int k, answer, a = 0;
    cin >> k;
    for (int i = 0; i <= 46; i += 1)
    {
        if (1 == i)
        {
            h[i] = 1;
        }
        else
        {
            h[i] = h[i-1] + h[i-2];
        }
    }
    answer = h[k];
    cout << answer;
    return 0;
}

谢谢！