fork(23) download 
  1. cache = {}
  2.  
  3. mod = 1000000009
  4.  
  5. def ans(n):
  6.     if cache.has_key(n):
  7.         return cache[n]
  8.  
  9.     if n == 0:
  10.         cache[n] = 1
  11.         return cache[n]
  12.     if n == 1:
  13.         cache[n] = 10
  14.         return cache[n]
  15.  
  16.     temp1 = ans(n/2)
  17.     temp2 = ans(n/2-1)
  18.  
  19.     if (n & 1) == 0:
  20.         cache[n] = (temp1*temp1 - temp2*temp2) % mod
  21.     else:
  22.         temp3 = ans(n/2 + 1)
  23.         cache[n] = (temp1 * (temp3 -temp2)) % mod
  24.  
  25.     return cache[n]
  26.  
  27. print ans(1000000000)
  28.  
Success #stdin #stdout 0s 9024KB
comments (?)
stdin 
Standard input is empty
stdout 
999049410
https://ideone.com/TNqxJw
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!