1 files changed, 44 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
new file mode 100644
index 0000000..2f2c839
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -0,0 +1,44 @@
+# Uses python3
+import sys
+
+def getFib(n):
+    if (n <= 1):
+        return n
+    fibLst = [None] * (n + 1)
+    fibLst[0] = 0
+    fibLst[1] = 1
+    for j in range(2, n + 1):
+        fibLst[j] = fibLst[j - 1] + fibLst[j - 2]
+    return fibLst[n]
+
+
+def getPisanoPeriod(m):
+    period = 2
+    remainder1 = 1
+    remainder2 = 1
+    
+    for i in range(3, 6 * m + 1):
+        period = period + 1
+        if (remainder2 == 1) & (remainder1 + remainder2 == m):
+            break
+        else:
+            tempHolder = remainder1 + remainder2
+            remainder1 = remainder2
+            if tempHolder >= m:
+                remainder2 = tempHolder - m
+            else:
+                remainder2 = tempHolder
+                
+    return period
+
+
+def getFibNModM(n, m):
+    p = getPisanoPeriod(m)
+    return getFib(n % p) % m
+
+if __name__ == '__main__':
+    entryNumbers = sys.stdin.read()
+    tokens = entryNumbers.split()
+    n = int(tokens[0])
+    m = int(tokens[1])
+    print(getFibNModM(n, m))
+\ No newline at end of file