1 files changed, 36 insertions, 0 deletions
diff --git a/euler_684.py b/euler_684.py
new file mode 100644
index 0000000..f5bbec7
--- /dev/null
+++ b/euler_684.py
@@ -0,0 +1,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()