[AtCoder ABC 129 C Typical Stairs] Pythonのロジックエラーについての質問

Question

前提・実現したいこと

Pythonで下記の問題を解いておりましたが、どうしてもある入力に対して間違いを出力します
どこのロジックが間違っているか、ご教示いただけますでしょうか
リンク内容

該当のソースコード

#------フィボナッチ数列の処理（上る段数に対する方法の数を数える）------------
def fibona(x):
    import math
    return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1))) // math.sqrt(5)

def main():
#-----inputの処理-------------------------
    n, m = map(int,input().split())
    mlis = []
    for _ in range(m):
        a = int(input())
        mlis.append(a)
    ans = 1
    mae = -1

    for i in range(m):

#------brokenは壊れている段、maeはその壊れている段の前の壊れている段。隣り合っていたらその時点で終了---------------
        broken = mlis[i]
        if mae == broken - 1:
            print(0)
            exit()

#------ひとつ前に壊れていた段の一つ上の段から、壊れている段のひとつ前の段まで登る登り方を求める--------------
        nobori = (broken-1) - (mae+1)
        if nobori == 0:
            ans *= 1
            mae = broken
        else:
            ans *= fibona(nobori)
            ans %= (10 ** 9 + 7)
            mae = broken

#-----すべての壊れている段を考え終えたら、最後の壊れている段の一つ上から、最終段まで登る登り方を数える-------
    nobori = n - (mae+1)
    ans *= fibona(nobori) 
    ans %= (10 ** 9 + 7)
    print(int(ans))

        

if __name__ == "__main__":
    main()

試したこと

サンプルすべてに対して正答を得ているのは確認していますが
本番の入力の一部について内部エラー（1入力分）と、誤答（2入力分）が発生しています
フィボナッチ数列の割り算（ルートで割るため誤差が出る？）や、整数の扱いの問題かとも思いましたが、今のところいずれも解決できていません
恐れ入りますが、ご教示いただけますでしょうか

Answer 1

ほとんど答えは出てますが、フィボナッチ数の計算に浮動小数点を使ってることが原因です。
浮動小数点を使うと上位15桁程度の精度しか出ませんし、この問題だと100000番目のフィボナッチ数が答えになることもあるので浮動小数点でも持て余します。

Comments

[sasuke_]

ご回答頂きありがとうございます
頂いた方針で、フィボナッチ数列の所を　

Decimal / Decimal

で処理しようとしましたが、これまでWAだったものの二つまでRE判定になりました（WA2, RE1だったものが、Decimal利用後にRE3判定）
申し訳ありませんが、REと処理される理由はお分かりになるでしょうか・・・？

[yudedako67]

fibona(100000)が正しく計算できることを確かめましたか?

[sasuke_]

ありがとうございました、おっしゃる通り、そもそもそちらで計算できないことを確認しました
確認不足で申し訳ありません。ご教示いただき、ありがとうございました