title: Calculating a huge fibonacci number modulo m in Python
body: <p>The goal of this problem is to calculate <strong>F[n] mod m</strong>. Here the inputs are <strong>n</strong> and <strong>m</strong>, where <strong>n</strong> stands for the index of the fibonacci number, say F[0] = 0, F[1] = 1, F[2] = 1, F[3]= 2 and <strong>m</strong> stands for the number by which <strong>F[n]</strong> will be divided. The constraints are:</p>
  
  <ul>
  <li>n >= 1 and n &lt;= 10^18</li>
  <li>m >= 2 and m &lt;= 10^5</li>
  </ul>
  
  <p>I have gone this problem so far and been able to generate the exact output of this problem except when I give 100000 as the value of <strong>m</strong>, it exceeds the time limit. The time limit is 5 seconds. If the value of <strong>m</strong> is given between and including from 2 to 99999, my program generates the correct output within the time limit. Any kind of help solving this problem would be highly appreciated.</p>
  
  <h2>Code:</h2>
  
  <pre><code>def fibonacci(n):
      if ( n == 0 ):
          return (0, 1)
      else:
          a, b = fibonacci(n/2)
          c = a * (2* b - a)
          d = a**2 + b**2
          if ( n % 2 ):
              return (d, c + d)
          else:
              return (c, d)
  
  
  def findRemainders(m):
      remainderList = ["0", "1"]
      i = 2
      while(1):
          firstFib, secondFib = fibonacci(i)
          if ( (firstFib % m) == 0 and (secondFib % m) == 1 ):
              break
          remainderList.append( (firstFib % m) )
          remainderList.append( (secondFib % m) )
          i += 2
  
      return remainderList
  
  
  def hugeFibonacciNumberModulo_m( n, m ):
      remainderList = findRemainders(m)
      length_of_period = len(remainderList)
      remainder = (n % length_of_period)
      out = remainderList[remainder]
      return out
  
  
  inp = map(int, raw_input().split())
  n, m = inp[0], inp[1]
  
  if ( (n &gt;= 1 and n &lt;= 10**18) and (m &gt;= 2 and m &lt;= 10**5) ):
      out = hugeFibonacciNumberModulo_m( n, m )
  print out
  </code></pre>