#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N; ll A[3010];
mint dp[3010][3010];  // dp[i][k] := i番目まででk組作った
mint tot[3010][3010]; // tot[k][mo] := k組作っていてこれまでの総和を(k+1)で割った余りがmoである
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    dp[0][0] = 1;
    tot[0][0] = 1;
    ll sum = 0;
    rep(i, 0, N) {
        sum += A[i];
        rep(k, 1, N + 1) dp[i + 1][k] = tot[k - 1][sum % k];
        rep(k, 1, N + 1) tot[k][sum % (k + 1)] += dp[i + 1][k];
    }
    
    mint ans = 0;
    rep(k, 1, N + 1) ans += dp[N][k];
    cout << ans << endl;
}






#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < (n);i++)
using namespace std;
const int INF = 10000000;
using ll = long long;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> x(m);

    vector<pair<int, int>> vw(n);

    rep(i, n) cin >> vw[i].second >> vw[i].first;

    rep(i, m) cin >> x[i];

    sort(vw.begin(), vw.end(), greater<pair<int, int>>());

    rep(i, q) {
        int l, r;
        cin >> l >> r;

        ll ans = 0;
        vector<pair<int, int>> vwtemp;
        for(auto j : vw) vwtemp.push_back(j);
        vector<int> temp;
        for(int j = 0;j < l - 1;j++) temp.push_back(x[j]);
        for(int j = r;j < m;j++) temp.push_back(x[j]);
    
        sort(temp.begin(), temp.end());    

        for(int j : temp){
            rep(k, n) {
                if(j >= vwtemp[k].second){
                    ans += vwtemp[k].first;
                    vwtemp[k].second = INF;
                    break;
                }  
            }
            
        }
        cout << ans << endl;

    }

    return 0;

}