title: Problems with modulo when calculating fibonacci
body: <p>I'm trying to solve a problem that requires me to calculate Fibonacci numbers up to 10^18 mod 10^9+7. The online judge is saying that I get right answers on the small cases (where the modulo isn't required), but in larger cases I get wrong answers.</p>
  
  <p>There is no problem with the algorithm otherwise, but the memoization aka saving the results into the dictionary <code>table</code> seems to have failed. I have no idea why.</p>
  
  <pre><code>luku = int(input())
  table = {0:0, 1:1, 2:1}
  
  def fib(num):
  
      if num in table:
          return table[num];
  
      if num % 2 == 0:
          puoli = num / 2;
          ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;
          table[num] = ans;
          return ans;
      else:
          puoli = (num-1) / 2;
          ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;
          table[num] = ans;
          return ans;
  
  
  print(fib(luku))
  </code></pre>
  
  <p>For example, with the input 54774730983471038 I'm getting 946469205 instead of the correct answer 795317107.</p>