Calculating Irrationals raised to some Power modulo 1000000007 Lets define a function F as
$F(n) = 1+(\frac{1+{\sqrt 5}}{2})^n$
As per wolfram site, ${\sqrt 5}\%99991=10104$
As per wolfram site, ${\sqrt 5}\%1000000007=no\_solution$
I need to find the value of $F(n)\%MOD $, where $MOD = 1000000007$ for very large $n<10^9$. Unfortunately ${\sqrt 5}\%MOD$ doesn't has an integer solution for $MOD = 1e9+7$. How shall I proceed?
 A: It looks like you're trying to compute Fibonacci numbers using a variant of Binet's formula (though you're forgetting to divide by $\sqrt5$ if that's your plan).
Unfortunately your approach to finding the remainder of the Fibonacci number doesn't really work here. I think you're trying to do modular reduction during the computation, applying the rule
$$ ab \bmod n = (a \bmod n)(b \bmod n) \bmod n$$
to push the modulo operations inwards in the computation.
Unfortunately the above rule only works when $a$ and $b$ are integers, and Binet's formula requires a power of a non-integer, so doing the entire computation modularly from the beginning is a non-starter.

A better way to compute modular Fibonacci numbers is the matrix equation
$$ \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^n = 
\begin{pmatrix}F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} $$
Because the matrices here always have integer entries you can do this computation modulo 1000000007 at each step. Combined with exponentiation by squaring this will allow you to compute modular Fibonacci numbers at feasible cost.

(Actually, the full Binet formula
$$ F_n = \frac{\bigl(\frac{1+\sqrt5}2\bigr)^n-\bigl(\frac{1-\sqrt5}2\bigr)^n}{\sqrt5} $$
will work in any field where the characteristic polynomial of $({}^1_1\,{}^1_0)$ splits -- that is, in any field of characteristic $\ne 2$ where $5$ has a square root -- but in general the right-hand power can't be replaced by a final round-to-integer step like it can in $\mathbb R$. So in principle you can use Binet's formula by doing your calculation in $\mathbb F_{1000000007^2}\cong\mathbb Z_{1000000007}[\sqrt 5]$ -- but it's not clear to me that this is more efficient than the matrix calculation above).
