#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define MAX_DIGITS 300

void reverse_str(char* str) {
    int n = strlen(str);
    for (int i = 0; i < n/2; i++) {
        char temp = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = temp;
    }
}

void add(const char* a, const char* b, char* result) {
    int carry = 0;
    int i;

    for (i = 0; a[i] || b[i] || carry; i++) {
        int digit_a = (a[i] && i < MAX_DIGITS) ? a[i] - '0' : 0;
        int digit_b = (b[i] && i < MAX_DIGITS) ? b[i] - '0' : 0;

        int sum = digit_a + digit_b + carry;
        result[i] = (sum % 10) + '0';
        carry = sum / 10;

        if (i >= MAX_DIGITS - 1 && carry) {
            fprintf(stderr, "Buffer overflow!\n");
            exit(1);
        }
    }
    result[i] = '\0';
}

int main() {
    clock_t start = clock();
    const int n = 1000;

    char a[MAX_DIGITS] = "0";
    char b[MAX_DIGITS] = "1";
    char sum[MAX_DIGITS];

    if (n == 1) {
        strcpy(b, "0");
    }
    else if (n == 2) {
        strcpy(b, "1");
    }
    else {
        for (int i = 3; i <= n; i++) {
            add(a, b, sum);
            strncpy(a, b, MAX_DIGITS);
            strncpy(b, sum, MAX_DIGITS);
        }
    }

    reverse_str(b);

    clock_t end = clock();
    printf("Time: %.3f ms\n", (double)(end - start) * 1000 / CLOCKS_PER_SEC);
    printf("Result: %s\n", b);

    return 0;
}