We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Prepare
- Mathematics
- Number Theory
- Fibonacci Finding (easy)

# Fibonacci Finding (easy)

# Fibonacci Finding (easy)

You're given three numbers: , , and , and all you have to do is to find the number where

As the number can be very large, output it modulo .

Consider the following link: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

**Input Format**

First line contains a single integer - the number of tests. lines follow, each containing three integers: , and .

**Constraints**

**Output Format**

For each test case output a single integer .

**Sample Input**

```
8
2 3 1
9 1 7
9 8 3
2 4 9
1 7 2
1 8 1
4 3 1
3 7 5
```

**Sample Output**

```
3
85
25
178
8
8
3
44
```

**Explanation**

First test case is obvious.

Let's look through the second one: