//                        YATIN KWATRA

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")


#define ll                      long long
#define ar                      array
#define sz(v)                   (int)(v.size())
#define inf                     1e18
#define int                     ll
#define FIO                     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ld                      long double
#define ull                     unsigned long long
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                     vector<int>
#define pq                      priority_queue
#define uomii                   unordered_map<int,int,best_hash>
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define mod                     1000000007
#define MIN                     -1e9
#define pi                      3.1415926535897932384626433832795
#define cz(x)                   63 - __builtin_clzll(x)

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


struct best_hash {
	static uint64_t splitmix64(uint64_t x) {

		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

const int N = 3e3 + 1;

int dp[N][N];
int v[N];
vii has[N][N]; // pos for remainder j from after i
int n;

int ways(int pos, int k) {
	if (pos == n + 1) return 1;
	int &ans = dp[pos][k];
	if (ans != -1) return ans;
	ans = 0;

	// now go to next k+1 or k

	int rem = v[pos - 1] % k;

	int idx = lower_bound(all(has[k][rem]), pos) - has[k][rem].begin();
	if (idx < sz(has[k][rem])) {
		int to = has[k][rem][idx];
		if (to < n) ans = (ways(to + 1, k) + ways(to + 1, k + 1)) % mod;
		else ans = ways(to + 1, k);
	}
	return ans;
}

void solve()
{
	cin >> n;
	fo(i, 1, n) cin >> v[i];

	memset(dp, -1, sizeof(dp));

	fo(i, 1, n) {
		int sum = 0;
		fo(j, 1, n) {
			sum += v[j];
			has[i][sum % i].pb(j);
		}
	}

	fo(i, 1, n) v[i] += v[i - 1];
	cout << ways(1, 1);
}

signed main() {

	FIO
	int t;
	t = 1;
	//cin >> t;
	fo(i, 0, t - 1) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define M 1005
#define LL long long
const LL mod = 1000000007;

int n;
LL f[M];
char Caa, Cab, Cba, Cbb;

inline LL qkpow (LL x, LL y){
	LL res = 1;
	while (y){
		if (y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
signed main (){
	scanf ("%d\n%c\n%c\n%c\n%c", &n, &Caa, &Cab, &Cba, &Cbb);
	if (n == 3 || n == 2){
		printf ("1\n");
		return 0;
	}
	f[1] = 2, f[2] = 3;
	for (int i = 3; i <= n; i ++)
		f[i] = (f[i - 1] + f[i - 2]) % mod;
	if (Cab == 'B'){
		if (Cbb == 'B')
			printf ("1\n");
		else{
			if (Cba == 'A'){
				printf ("%lld\n", qkpow (2, n - 3));
			}
			else{
				printf ("%lld\n", f[n - 3]);
			}
		}
	}
	else{
		if (Caa == 'A')
			printf ("1\n");
		else{
			if (Cba == 'B'){
				printf ("%lld\n", qkpow (2, n - 3));
			}
			else{
				printf ("%lld\n", f[n - 3]);
			}
		}
	}
	return 0;
}