>author: Utin

## Question

史蒂夫與戴夫都使用eToro投資金融市場，史帝夫鑽研全球投資機會，發現有一檔叫做 "費波納契指數ETF"，此ETF有一個特點，他會遵照費氏數列的規則增加，但是一旦價格超過 100000，那麼價格就會跌落至 "超過時的價格 % 100000"，史蒂夫想知道此ETF過去的價格波動，請你幫他算出歷年來的價格。

### Input
有一個整數N，代表需要輸出幾項費氏數列的數字

### Output
倒著輸出 N 項費氏數列，每項以空格隔開，最後一個數字後面需輸出'\n'(最後一個數字後面不要輸出空格)
由於數字會超過int的範圍，**請做完每項運算後對 100000 取餘數**

### Constraint
1 <= N <= 3000

### Sample Input

10

51

### Sample Output

55 34 21 13 8 5 3 2 1 1

11074 69025 42049 26976 15073 11903 3170 8733 94437 14296 80141 34155 45986 88169 57817 30352 27465 2887 24578 78309 46269 32040 14229 17811 96418 21393 75025 46368 28657 17711 10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1

## 作法
可以用遞迴或是迴圈搭配陣列

## 常見問題
- scanf 記得取址
- 輸出是從末項到首項
- 記得要對100000取餘數，若不確定問題出在哪，請在每個 assign 的地方最後都加上 %100000

## 解法 - 遞迴

#include <stdio.h>

int K;

int rec(int a, int b, int k);

int main() {
    scanf("%d", &K);
    rec(0, 1, K);
}

int rec(int a, int b, int k) {
    if (k == 1) {
        printf("%d", b);
        printf(k == K ? "\n" : " ");
        return b;
    }
    int rt = rec(b % 100000, (a + b) % 100000, k - 1);
    printf("%d", b);
    printf(k == K ? "\n" : " ");
    return rt;
}

## 解法 - 迴圈 + 陣列

#include <stdio.h>

int main() {
    int N, i, list[3000];

    scanf("%d", &N);
    list[0] = list[1] = 1;
    
    for (i = 2; i < N; i++)
        list[i] = (list[i - 1] + list[i - 2]) % 100000;
    
    for (i = N - 1; i >= 0; i--) {
        printf("%d", list[i]);
        printf(i == 0 ? "\n" : " ");
    }
}