FIB128  128bitFibonacci
Warning
This task is intended to help people to debug their codes and try speed experiments.
The task is the same as in some known problems, but with new constraints and speed goal.
The Fibonacci sequence is defined for any positive integer by :
If N<2: Fib(N)=N, else Fib(N)=Fib(N1)+Fib(N2)
You have the task of being the fastest to compute Fib(N) mod M.
Input
The input consists of 500,000 lines.
In each the 500,000 lines there are two integers N, M.
You don't need to read the whole input, only some lines to get some points.
You should begin with one line, then 10, then 100, ...
Output
For as many test cases you can, on a single line, print Fib(N) mod M.
Example
Input: 5 4 5 5 5 6 [...] Output: 1 0 5
Constraints
0 <= N <= 10^38 2 <= M <= 10^38
Score
As in the example, if you can output the 3 first correct answers, your score will be 3 points. No need to solve all the input, the minimum is 1 ; every solver in any language will be able to check his FIB128speed.
hide comments
Paulo Roberto Santos de Sousa:
20190408 05:07:54
is there some 256 bit integer in c/c++ or I will have to implement bigint algorithm to solve the problem?


Fancy Mouse:
20171109 12:50:53
pro tip: use clang. gcc optimization heuristics is horribly broken. 

[Lakshman]:
20170301 08:45:10
Why TLE. I am using ************, and on IDEONE I am getting correct output.


Michael Kharitonov:
20170219 18:33:21
Yep, my method is a dead end, 10^38 is too much!

Added by:  Francky 
Date:  20170214 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  FIB64 