# UVa 10229

## Summary

Get the F(n) Fibonacci's Number then get its modulo on ${\displaystyle 2^{m}}$.

## Explanation

Solving this problem requires you to calculate Fibonacci in lg(n) time. It's by dividing n into n/2 size problem at each instance.

## Gotchas

• Use a 64 bit integer representation for the Fibonacci's number as a 32 bit will overflow.
• Use the Q-Fibonacci Matrix to get the output in O(log n) and avoid TLE.

```11 7
11 6
```

```89
25
```