@@ -0,0 +1,588 @@
+'''%0AFast Doubling method: https://www.hackerearth.com/practice/notes/fast-doubling-method-to-find-nth-fibonacci-number/%0A%0AFibonacci series: 0 1 1 2 3 ...%0ANthFibonacci(n, mod) -%3E int%0Amod: We find modulo of number (usually with 1e9+7), as it is too big.%0A'''%0A%0Adef NthFibonacci(n, mod):%0A%09return int(NthFibonacciHelper(n, mod)%5B0%5D)%0A%0Adef NthFibonacciHelper(n, mod):%0A%09if not n:%0A%09%09return (0, 1)%0A%09else:%0A%09%09a, b = NthFibonacciHelper(n // 2, mod)%0A%09%09c = (a%25mod * ((b*2)%25mod - a%25mod))%25mod%0A%09%09d = ((a%25mod * a%25mod)%25mod + (b%25mod * b%25mod)%25mod)%25mod%0A%0A%09%09if not n&1:%0A%09%09%09return (c, d)%0A%09%09else:%0A%09%09%09return (d, c + d)%0A

Create fastDoublingNthFibonacci.py