blob: f5bbec7913abf834f4a25a445e58938403517c09 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#!/usr/bin/env python
_mod = 1000000007
def expmod(a,n,m):
if n == 0:
return 1
if n % 2 == 0:
t = expmod(a,n>>1,m)
return (t*t)%m
else:
return (a*expmod(a,n-1,m))%m
def S(k):
n = k // 9
m = k % 9
pwr = expmod(10,n,_mod)
return 5*(pwr-1)-9*n+pwr*(m+2)*(m+1)//2-(m+1)
def main():
fib = [0]*91
fib[0] = 0
fib[1] = 1
for i in range(2,91):
fib[i] = fib[i-2]+fib[i-1]
ans = 0
for i in range(2,91):
print(i)
ans = (ans + S(fib[i])) % _mod
print(ans)
if __name__ == "__main__":
main()
|
