結果

問題 No.147 試験監督（2）
コンテスト
ユーザー Hachimori
提出日時 2015-02-09 00:05:36
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 1,013 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 29,328 KB
最終ジャッジ日時 2024-06-23 08:24:51
合計ジャッジ時間 6,714 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python
#coding:utf8

MOD = 1000000007

def read():
    N = input()
    cdList = []
    for i in range(N):
        cdList.append(map(int, raw_input().split()))
    return cdList


def matmul(a, b):
    c = [[0 for j in range(len(b[0]))] for i in range(len(a))]

    for i in range(len(a)):
        for j in range(len(b[0])):
            toAdd = 0
            for k in range(len(a[0])):
                toAdd = (toAdd + a[i][k] * b[k][j]) % MOD
            c[i][j] = toAdd

    return c


def matpow(p, n):
    if n == 0:
        return [[1, 0], [0, 1]]

    t = matpow(p, n / 2)

    return matmul(matmul(t, t), p) if n & 1 else matmul(t, t)


def mypow(p, n):
    if n == 0:
        return 1
        
    t = mypow(p, n / 2)

    return t * t * p % MOD if n & 1 else t * t % MOD


def work(cdList):
    ans = 1
    
    for C, D in cdList:
        mat = matpow([[1, 1], [1, 0]], C + 2)
        ans = ans * mypow(mat[0][1],  D) % MOD
    
    print ans


if __name__ == "__main__":
    work(read())
0