I thought I would take the chance to provide the general solution to all of these puzzles.

If anyone has any questions I can motivate the solution here.

```
#! /usr/bin/env nix-shell
#! nix-shell -p "haskell.packages.ghc822.ghcWithPackages (pkgs: [pkgs.matrix])" -i "cabal exec -- runghc"

module Main where

import Control.Applicative ((<\$>))
import qualified Data.Matrix as Matrix
import Data.Matrix ((<->))

dot :: Num a => Matrix.Matrix a -> Matrix.Matrix a -> Matrix.Matrix a
dot = Matrix.multStd

matrixExp :: Integral a => Matrix.Matrix a -> Integer -> a -> Matrix.Matrix a
matrixExp m n modulus
| n <= 0    = Matrix.identity (Matrix.nrows m)
| odd n     = (`mod` modulus) <\$> m `dot` (matrixExp m (n-1) modulus)
| otherwise = (`mod` modulus) <\$> mHalfN `dot` mHalfN
where mHalfN = matrixExp m (n `div` 2) modulus

series :: [Integer] -> Integer -> Integer -> Integer
series coeffs n modulus = Matrix.getElem 1 1 \$ (matrixExp u n modulus)
where
m = length coeffs
u = Matrix.fromLists [coeffs]
<->
(Matrix.extendTo 0 (m - 1) l \$ Matrix.identity (m - 1))

fib :: Integer -> Integer -> Integer
fib = series [1,1]

pell :: Integer -> Integer -> Integer
pell = series [2,1]

trib :: Integer -> Integer -> Integer
trib = series [1,1,1]

extreme :: Integer -> Integer -> Integer
extreme = series [1,1,0,0,5,0,0,0,3]

main :: IO ()
main = do
putStrLn \$ "MD 1:     " ++ show (fib 10 (10^10))
putStrLn \$ "MD 2:     " ++ show (fib (10^7) (10^10))
putStrLn \$ "MD 2 (*): " ++ show (fib (10^100) (10^10))
putStrLn \$ "MD 3:     " ++ show (pell (10^7) (10^10))
putStrLn \$ "MD 3 (*): " ++ show (pell (10^100) (10^10))
putStrLn \$ "MD 4:     " ++ show (trib (10^7) (10^10))
putStrLn \$ "MD 4 (*): " ++ show (trib (10^100) (10^10))
putStrLn \$ "MD 5:     " ++ show (extreme (10^7) (10^10))
putStrLn \$ "MD 5 (*): " ++ show (extreme (10^100) (10^10))
```

This outputs:

```
MD 1:     89
MD 2:     7120937501
MD 2 (*): 2460937501
MD 3:     4570126209
MD 3 (*): 9020126209
MD 4:     7912206465
MD 4 (*): 6198029313
MD 5:     6777244134
MD 5 (*): 4404226404
```