using System;

using System.Numerics;

​

class Program {

    static void Main() {

        Console.Write("Enter the position of the Fibonacci sequence: ");

        int n = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine(

            $"The {n}th number in the Fibonacci sequence is {Fibonacci(n)}");

    }

​

    static BigInteger Fibonacci(int n) {

        BigInteger[, ] F = new BigInteger[, ]{{1, 1}, {1, 0}};

        if (n == 0) return 0;

        Power(F, n - 1);

        return F[0, 0];

    }

​

    static void Multiply(BigInteger[, ] F, BigInteger[, ] M) {

        BigInteger x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0];

        BigInteger y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1];

        BigInteger z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0];

        BigInteger w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1];

​

        F[0, 0] = x;

        F[0, 1] = y;

        F[1, 0] = z;

        F[1, 1] = w;

    }

​

    static void Power(BigInteger[, ] F, int n) {

        if (n == 0 || n == 1) return;

        BigInteger[, ] M = new BigInteger[, ]{{1, 1}, {1, 0}};

​

        Power(F, n / 2);

        Multiply(F, F);

​

        if (n % 2 != 0) Multiply(F, M);

    }

}

​