Console.Write("Enter the position of the Fibonacci sequence: ");
int n = Convert.ToInt32(Console.ReadLine());
$"The {n}th number in the Fibonacci sequence is {Fibonacci(n)}");
static BigInteger Fibonacci(int n) {
BigInteger[, ] F = new BigInteger[, ]{{1, 1}, {1, 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];
static void Power(BigInteger[, ] F, int n) {
if (n == 0 || n == 1) return;
BigInteger[, ] M = new BigInteger[, ]{{1, 1}, {1, 0}};
if (n % 2 != 0) Multiply(F, M);