Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
Given integers A and B, calculate Fib(A ** B) % 10000103.

The Fibonacci sequence is defined by the following recursive formula:

F(0) = 0
F(1) = 1
F(N) = F(N−1) + F(N−2) for N ≥ 2

Write a function:

class Solution { public int solution(int N, int M); }

that, given two non-negative integers N and M, returns a remainder of F(NM) modulo 10,000,103.
Note: 10,000,103 is a prime number.

For example, given N = 2 and M = 3, the function should return 21, since 23 = 8 and F(8) = 21.

Write an efficient algorithm for the following assumptions:

  • N and M are integers within the range [0..10,000,000].
Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.