SPOJ - POWFIB (Fibo and non fibo) Time Limit Exceeds
Here, you are using modular exponentiation and modular multiplication, which are fast enough.
Your nonfibo function is also taking only O(lg(n)) time.
But your method for computing nth fibonacci number is not much efficient. Try using this Linear Recurrence Solving Method.