WA in RESSTNCE

[zapper_awake]

Problem : spoj.com/problems/

Code : ideone.com/AKT4eU

import numpy as np
from numpy import linalg as LA
from fractions import gcd
def expo(A , m):
	if m==1:
		return A
	#print A
	p = 1
	for x in np.nditer(A):
		p = gcd(p,x)
	A /= p
	#A /= gcd( gcd(A[1][0],A[1][1] ),gcd(A[0][0],A[0,1] ) )
	C = np.matrix( "0,0 ; 0,0")
	#print C
	if ~m&1:
		C =  expo(A,m/2)*expo(A,m/2)
		return C
	else:
		C = A*expo(A,m/2)
		return C
A = np.matrix( "1,1 ; 1,2")
B = np.matrix( " 1;1")
t= input()
while t:
	t-=1
	n,mod = map(int,raw_input().split())
	if n==1:
		print "1/1"
	else:
		print (expo(A,n-1)*B) % mod

Approach : using matrix
[ 1 1 ] * [ A[n-1] ] = [ A[n] ]
[1 2 ] * [ B[n-1] ] = [ B[n] ]

Div the matrix by Gcd ( a11, a12 , a21 ,a 22) along to avoid overflow

I think my logic is correct , any hints to what i have done wrong? , is the matrix correct? , Please help!

[francky]

I think your matrix is OK.
You have overflow in your code,
I'm not sure but numpy translate your data into float. (with maybe 50bit of mantissa)
You should work without numpy, it will be easier.
Try to compute few terms by hand, you should see something...

[zapper_awake]

Thanks a lot francky

Yes numpy does convert values in float , so we can't have big integers in a numpy matrix .
Finally AC ,with C++ at 0.00sec .

However i am not able to do via python. I get TLE with the same implimentation. Any tricks on how to do fast matrix multiplication in python? , i see you have done many problems in python way faster than others , any secrets ?