title: Nth Fibonacci number for n as big as 10^19?
body: <p>I am trying to make a program to find the nth Fibonacci number for 1 &lt; n &lt; 10^19.</p>
  
  <p>Here is my code using dynamic programming.</p>
  
  <pre><code>memo = {}
  def fib(n):
      if n in memo:
          return memo[n]
      if n &lt;= 2:
          f = 1
      else:
          f = fib(n-1) + fib(n-2)
      memo[n]=f
      return f
  print fib(input()) % 1000000007
  </code></pre>
  
  <p>My code does not seem to work for large numbers. I get invalid response error.
  Any suggestions?</p>