#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define run ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned ll
#define ld double
#define endl "\n"
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
#define N 100007
#define minimum -9223372036854775807
#define maximum -minimum
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
template <class t>
using ordered_set=tree<t, null_type,less_equal<t>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
ll lcm(ll a, ll b)
{
return a/gcd(a, b)*b;
}
bool isprime(ll n)
{
if(n==1)
return 0;
for(ll i=2; i*i<=n; i++)
{
if(n%i==0)
return 0;
}
return 1;
}
ll binpow(ll a, ll b)
{
a%=mod;
ll res=1;
while(b>0)
{
if(b%2==1)
res=(res*a)%mod;
a=(a*a)%mod;
b/=2;
}
return res;
}
ll dp[N];
const int modd=1000007;
int main()
{
run;
ll n;
cin>>n;
vector<ll>a(n+1);
for(ll i=1; i<=n; i++)
{
cin>>a[i];
}
if(n==2)
{
if(a[0]==1 && a[1]==1)
cout<<"1\n";
else
cout<<"2\n";
}
else if(n==3)
{
if(a[0]==1 && a[1]==1 && a[2]==1)
cout<<1;
if(a[0]==1 && a[1]==1 && a[2]==2)
cout<<2;
if(a[0]==1 && a[1]==2 && a[2]==1)
cout<<3;
if(a[0]==1 && a[1]==2 && a[2]==2)
cout<<4;
if(a[0]==1 && a[1]==2 && a[2]==3)
cout<<5;
}
else if(n==4)
{
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1)
cout<<1;
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2)
cout<<2;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1)
cout<<3;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2)
cout<<4;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3)
cout<<5;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1)
cout<<6;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2)
cout<<7;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1)
cout<<8;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2)
cout<<9;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3)
cout<<10;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2)
cout<<11;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3)
cout<<12;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4)
cout<<13;
}
if(n==5)
{
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1 && a[4]==1) //11111
cout<<1;
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1 && a[4]==2) //11112
cout<<2;
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==1) //11121
cout<<3;
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==2) //11122
cout<<4;
if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==2 && a[4]==3) //11123
cout<<5;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1 && a[4]==1) //11211
cout<<6;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==1 && a[4]==2) //11212
cout<<7;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==1) //11221
cout<<8;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==2) //11222
cout<<9;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==2 && a[4]==3) //11223
cout<<10;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==2) //11232
cout<<11;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==3) //11233
cout<<12;
if(a[0]==1 && a[1]==1 && a[2]==2 && a[3]==3 && a[4]==4) //11234
cout<<13;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1 && a[4]==1) //12111
cout<<14;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==1 && a[4]==2) //12112
cout<<15;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==1) //12121
cout<<16;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==2) //12122
cout<<17;
if(a[0]==1 && a[1]==2 && a[2]==1 && a[3]==2 && a[4]==3) //12123
cout<<18;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1 && a[4]==1) //12211
cout<<19;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==1 && a[4]==2) //12212
cout<<20;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==1) //12221
cout<<21;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==2) //12222
cout<<22;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==2 && a[4]==3) //12223
cout<<23;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==2) //12232
cout<<24;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==3) //12233
cout<<25;
if(a[0]==1 && a[1]==2 && a[2]==2 && a[3]==3 && a[4]==4) //12234
cout<<26;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==1) //12321
cout<<27;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==2) //12322
cout<<28;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==2 && a[4]==3) //12323
cout<<29;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==2) //12332
cout<<30;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==3) //12333
cout<<31;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==3 && a[4]==4) //12334
cout<<32;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==3) //12343
cout<<33;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==4) //12344
cout<<34;
if(a[0]==1 && a[1]==2 && a[2]==3 && a[3]==4 && a[4]==5) //12345
cout<<35;
}
dp[1]=1;
dp[2]=2;
dp[3]=5;
dp[4]=13;
ll pref[n+1];
pref[1]=1;
pref[2]=3;
pref[3]=8;
pref[4]=21;
for(ll i=5; i<=n; i++)
{
dp[i]=pref[i-1]+dp[i-1]%modd;
dp[i]++;
pref[i]=pref[i-1]+dp[i];
pref[i]%=modd;
}
cout<<dp[n]%modd<<endl;
}
/*
1 - 1
2 - 2
3 - 5
4 - 13
5 - 35
1
1 1
2
1 1 1
1 2 2
3
1 1 1 1
1 1 2 2
1 2 1 3
1 2 2 4
1 2 3 5
4
1 1 1 1 1
1 1 1 2 2
1 1 2 1 3
1 1 2 2 4
1 1 2 3 5
1 2 1 1 6
1 2 1 2 7
1 2 2 1 8
1 2 2 2 9
1 2 2 3 10
1 2 3 2 11
1 2 3 3 12
1 2 3 4 13
5
1 1 1 1 1 1
1 1 1 1 2 2
1 1 1 2 1 3
1 1 1 2 2 4
1 1 1 2 3 5
1 1 2 1 1 6
1 1 2 1 2 7
1 1 2 2 1 8
1 1 2 2 2 9
1 1 2 2 3 10
1 1 2 3 2 11
1 1 2 3 3 12
1 1 2 3 4 13
1 2 1 1 1 14
1 2 1 1 2 15
1 2 1 2 1 16
1 2 1 2 2 17
1 2 1 2 3 18
1 2 2 1 1 19
1 2 2 1 2 20
1 2 2 2 1 21
1 2 2 2 2 22
1 2 2 2 3 23
1 2 2 3 2 24
1 2 2 3 3 25
1 2 2 3 4 26
1 2 3 2 1 27
1 2 3 2 2 28
1 2 3 2 3 29
1 2 3 3 2 30
1 2 3 3 3 31
1 2 3 3 4 32
1 2 3 4 3 33
1 2 3 4 4 34
1 2 3 4 5 35
*/
// By Xanlar
// nece helldi?
