Fibonacci?

import java.util.*;
import java.math.BigInteger;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger n = sc.nextBigInteger();

        boolean isFib = true;

        for(int p = 1; p <= 100; ++p) {
            BigInteger prime = BigInteger.valueOf(p);
            if(prime.isProbablePrime(10)) {
                int r = n.mod(prime).intValue();
                int val1 = (5 * r * r - 4) % p;
                int val2 = (5 * r * r + 4) % p;
                if(!(val1 == 0 || modExp(val1, (p - 1) / 2, p) == 1 || val2 == 0 || modExp(val2, (p - 1) / 2, p) == 1)) {
                    isFib = false;
                }
            }
        }

        if(isFib) {
            System.out.println("SIM");
        } else {
            System.out.println("NAO");
        }
    }

    static int modExp(int a, int e, int m) {
        int ans = 1;
        while(e != 0) {
            if((e & 1) != 0)
                ans = (ans * a) % m;
            a = (a * a) % m;
            e /= 2;
        }
        return ans;
    }
}