結果

問題 No.147 試験監督（2）
ユーザー lam6er
提出日時 2025-03-20 20:20:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 826 ms / 2,000 ms
コード長 1,004 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 111,864 KB
最終ジャッジ日時 2025-03-20 20:21:54
合計ジャッジ時間 4,135 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7
PHI = MOD - 1

def fib(n, mod):
    def fast_doubling(n):
        if n == 0:
            return (0, 1)
        a, b = fast_doubling(n // 2)
        c = (a * (2 * b - a)) % mod
        d = (a * a + b * b) % mod
        if n % 2 == 1:
            return (d, (c + d) % mod)
        else:
            return (c, d)
    return fast_doubling(n)[0]

def mod_string(s, m):
    res = 0
    for c in s:
        res = (res * 10 + int(c)) % m
    return res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    product = 1
    for _ in range(N):
        C_k = int(input[ptr])
        ptr += 1
        D_str = input[ptr]
        ptr += 1
        n = C_k + 2
        a = fib(n, MOD)
        if a == 0:
            contrib = 0
        else:
            exponent = mod_string(D_str, PHI)
            contrib = pow(a, exponent, MOD)
        product = (product * contrib) % MOD
    print(product % MOD)

if __name__ == "__main__":
    main()
0