BigFibonacci | Topcoder Archive

Problem Statement

Depicted below is the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

As you can see, each value from 2 on is the sum of the previous two values. Given the 0-based index of a Fibonacci number and an int M, return the index-th Fibonacci number modulo M.

Definition

Class:: BigFibonacci
Method:: fibNumber
Parameters:: String, int
Returns:: int
Method signature:: int fibNumber(String index, int M)
(be sure your method is public)

Constraints

index will be an integer between 0 and 1015, inclusive, with no extra leading zeroes.
M will be between 1 and 1000000 (106).

Examples

```
"7"
```
```
10
```
```
Returns: 3
```
```
"5"
```
```
1
```
```
Returns: 0
```
```
"0"
```
```
23
```
```
Returns: 0
```
```
"17"
```
```
2
```
```
Returns: 1
```
```
"54"
```
```
341890
```
```
Returns: 177022
```
F54 = 86267571272. 86267571272 % 341890 = 177022.
```
"300"
```
```
77531
```
```
Returns: 0
```
F300 = 222232244629420445529739893461909967206666939096499764990979600.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.