FibonacciMatrix

package main

import (
	"fmt"
	"math/big"
)

func fib(n int) *big.Int {
	a := big.NewInt(1)
	b := big.NewInt(1)
	c := big.NewInt(1)
	rc := big.NewInt(0)
	d := big.NewInt(0)
	rd := big.NewInt(1)
	for  ; n > 0;{
		if n % 2 != 0 {
			tc := rc
			//rc = rc * a + rd * c
			rc1 := new(big.Int).Add(new(big.Int).Mul(rc,a) , new(big.Int).Mul(rd,c))
			rc = rc1
			//rd = tc * b + rd * d
			rd1 := new(big.Int).Add(new(big.Int).Mul(tc, b) , new(big.Int).Mul(rd, d))
			rd = rd1
		}
		ta := a
		//fmt.Println("ta = ",ta)
        tb := b
        //fmt.Println("tb = ",tb)
        tc := c
        //fmt.Println("tc = ",tc)
        //a = a*a  + b*c
        a = new(big.Int).Add(new(big.Int).Mul(a, a), new(big.Int).Mul(b, c))
        //fmt.Println("a = ",a)
        //b = ta*b + b*d
        b= new(big.Int).Add(new(big.Int).Mul(ta,b) , new(big.Int).Mul(b,d))
        //c = c*ta + d*c
        //fmt.Println("b = ",b)
        c = new(big.Int).Add(new(big.Int).Mul(c,ta) , new(big.Int).Mul(d,c))
        //d = tc*tb+ d*d
        //fmt.Println("c = ",c)
        d = new(big.Int).Add(new(big.Int).Mul(tc,tb) , new(big.Int).Mul(d,d))
        //fmt.Println("d = ",d)
        n >>= 1

	}
	return rc
}


func main(){
	var n int
	fmt.Scan(&n)
	fmt.Print(fib(n))
}