/// hhoangcpascal

#include <iostream>
#include <algorithm>
#define llong long long

using namespace std;

const llong mod = 1e9+7;
llong prefix[3006], dp[3006][3006], tmp[3006];
int n;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; ++i) {
        llong a; cin >> a;
        prefix[i] = prefix[i-1] + a;
    }

    for(int i = 1; i <= n; ++i) dp[1][i] = 1;

    for(int i = 2; i <= n; ++i) {
        fill(tmp, tmp+i, 0LL);

        tmp[prefix[i-1] % i] = dp[i-1][i-1];
        for(int j = i; j <= n; ++j) {
            (dp[i][j] += tmp[prefix[j] % i]) %= mod;
            (tmp[prefix[j] % i] += dp[i-1][j]) %= mod;
        }
    }

    llong ans = 0;
    for(int i = 1; i <= n; ++i) (ans += dp[i][n]) %= mod;

    cout << ans;

    return 0;
}

//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*                                                    
      I ♥ CLARICE STARLING...                                                               
        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
const ll INF = (ll)2e18 + 77;
vector<int>d[10];
void precompute()
{
    d[0].pb(0);
    ll i;
    foe(i,1,9)
    {
        unordered_set<ll>x;
        ll now=i;
        while(true)
        {
            if(x.count(now%10))break;
            d[i].pb(now%10);
            x.insert(now%10);
            now*=i;
        }
    }
}
ll modularExponentiation(ll x,ll n,ll M)
{   
    ll result=1ll;
    while(n>0)
    {
        if(n % 2 ==1)
        result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return (result-1+M)%M;
}
void solve()
{
   ll A,B,C;cin>>A>>B>>C;
   A=A%10;
   ll p=modularExponentiation(B,C,sz(d[A]));
   cout<<d[A][p]<<"\n";
    
}
int main()
{
   fastio
   precompute();
   //Test_cases
   solve();
  return 0;
}
