(逆元・フェルマーの小定理)ARC-020-C-A mod B Problem(99点解法)

問題URL→http://arc020.contest.atcoder.jp/tasks/arc020_3

初めて逆元・フェルマーの小定理を自力で書いたかもしれない。
逆元はA/B mod pを求めるときにBで割る代わりにBの逆元B^-1を掛けるA*B^-1 mod pで余りが求められるというもの。
フェルマーの小定理はpが素数の場合、xの逆元はx^(p-2)であるというもの。

(自分用→詳しくはノート参照)

(コードID:9832)

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;
int a[10101], L[10101];
int B;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> a[i] >> L[i];
    }
    cin >> B;

    if (B != MOD) return 0;

    int amari = 0;
    REP(i,N) {
        amari *= mod_pow(10, to_string(a[i]).length() * L[i], MOD);

        int bunsi = mod_pow(
                        mod_pow(10, to_string(a[i]).length(), MOD),
                        L[i],
                        MOD);
        bunsi -= 1;
        if (bunsi < 0) bunsi += MOD;

        int inv = mod_pow(10, to_string(a[i]).length(), MOD);
        inv -= 1;
        if (inv < 0) inv += MOD;
        inv = mod_pow(inv, MOD - 2, MOD);   //フェルマーの小定理

        int tempAmari = a[i] * bunsi;
        tempAmari %= MOD;
        tempAmari *= inv;
        tempAmari %= MOD;

        amari += tempAmari;
        amari %= MOD;
    }

    cout << amari << endl;
}