// #ifndef _GLIBCXX_DEBUG
// #define NDEBUG
// #endif
#include<iostream>
#include<array>
#include<vector>
#include<algorithm>
#include<cassert>
#include<set>
#ifdef _GLIBCXX_DEBUG
#include<sstream>
#define cin cin_
namespace std{
std::stringstream cin(R"(
4
4 1 1 5
)");
};
#endif
int constexpr MOD=1000000007;
template<int M,int N>
struct Matrix{
std::array<std::array<int,N>,M> a;
std::array<int,N>& operator[](int r){return a[r];}
Matrix operator+(Matrix b)const{
Matrix ans;
for(int r=0;r<M;++r)for(int c=0;c<N;++c){
int x=a[r][c]+b[r][c];
if(x>=MOD)x-=MOD;
ans[r][c]=x;
}
return ans;
}
Matrix operator-(Matrix b)const{
Matrix ans;
for(int r=0;r<M;++r)for(int c=0;c<N;++c){
int x=a[r][c]-b[r][c];
if(x<0)x+=MOD;
ans[r][c]=x;
}
return ans;
}
template<int P>
Matrix operator*(Matrix<N,P> b)const{
Matrix<M,P> ans{};
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
for(int k=0;k<P;++k){
int& x=ans[i][k];
x=(a[i][j]*(int64_t)b[j][k]+x)%MOD;
}
return ans;
}
};
Matrix<2,2> trmat(int diff){
/*
Given a Matrix<1,2> with {{f0,f1}}, multiply it by trmat(diff)
to get the matrix of next i value.
*/
assert(diff<MOD&&diff>=2);
return Matrix<2,2>{{{
{diff/2ull, 1},
{(diff-1)/2ull,1}
}}};
}
struct ST{
struct Node{
// represent a range of nodes
Matrix<2,2> tr;
int min,max;
Node():min(-1){
// (empty set)
}
Node(int val):tr{{{
{1,0},{0,1}
}}},min(val),max(val){
assert(0<=val);
}
bool empty()const{
return min<0;
}
Node(Node l,Node r){
if(l.empty())
*this=r;
else if(r.empty())
*this=l;
else{
tr=l.tr*trmat(r.min-l.max)*r.tr;
min=l.min;
max=r.max;
}
}
};
std::vector<Node> d;
std::vector<int> vals;
int ofs; // offset - how valindex coer to index on (d) (see index func below)
int index(int valindex)const{
valindex+=ofs;
if(valindex>=d.size())valindex-=d.size()/2;
return valindex;
}
ST(std::vector<int> _vals):
d(_vals.size()*2), // initially all nodes are empty
vals(std::move(_vals))
{
int const n=vals.size();
ofs=1;
while(ofs<n)ofs*=2;
assert(n>0);
// for(int i=0;i<n;++i)
// d[index(i)]=Node(vals[i]);
// for(int i=n-1;i;--i)
// d[i]=Node(d[i<<1],d[i<<1|1]);
}
int get()const{
Node root=d[1];
assert(!root.empty());
int s0=root.min;
Matrix<1,2> f0{{{
{s0/2u,1}
}}}; // f[i=0]
auto fn=f0*root.tr;
return (fn[0][0]+fn[0][1])%MOD;
}
void set(int val,bool on){
auto it=std::lower_bound(begin(vals),end(vals),val);
assert(*it==val);
int ind=index(it-begin(vals));
bool currently_on=!d[ind].empty();
assert(on!=currently_on);
if(on)
d[ind]=Node(val);
else
d[ind]=Node();
for(ind>>=1;ind;ind>>=1)
d[ind]=Node(d[ind<<1],d[ind<<1|1]);
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int n;std::cin>>n;
std::vector<int> a(n);
for(int& x:a){
std::cin>>x;
--x;
}
std::set<int> s; // zeckendorf repr
struct Event{
enum Type{
ADD,REMOVE,QUERY
};
Type t;
int n;
};
std::vector<Event> evs;
std::vector<int> stk;
for(int x:a){
// add F[x] to s
assert(stk.empty());
stk.push_back(x);
#define x DONT_USE_THIS
do{ // TODO: reduce (nnum*log) to (nnum+log)
int y=stk.back();stk.pop_back();
auto it=s.lower_bound(y-1);
if(it==s.end()||*it>y+1){
s.insert(y);
evs.push_back({Event::ADD,y});
}else if(*it<y){
assert(*it==y-1);
evs.push_back({Event::REMOVE,*it});
s.erase(it);
stk.push_back(y+1);
}else if(*it==y){
evs.push_back({Event::REMOVE,*it});
s.erase(it);
stk.push_back(y+1);
if(y==0){ // assume F[-1] == 1 and F[-2] == 0
assert(y-2 == -2);
continue;
}else
stk.push_back(std::max(0,y-2));
}else{
assert(*it==y+1);
evs.push_back({Event::REMOVE,*it});
s.erase(it);
stk.push_back(y+2);
}
}while(!stk.empty());
evs.push_back({Event::QUERY,0});
/* // how to compute a query the naive way
int const n=s.size();
std::vector<int> f0(n),f1(n);
assert(n>0);
int s0=*s.begin();
f0[0]=s0/2u; // [i] = number of repr of [0..i] -> F{x | x<s[i]}
f1[0]=1; // ~~~ but with F(s[i])
auto it=s.begin();++it;
for(int i=1,
last=s0; // s[i-1]
it!=s.end();++i,last=*it++){
int diff=*it-last; // s[i]-s[i-1]
f1[i]=(
f0[i-1]+f1[i-1]
)%MOD;
f0[i]=(
f0[i-1]*(diff/2ull)+f1[i-1]*((diff-1)/2ull)
)%MOD;
}
std::cout<<(f0.back()+f1.back())%MOD<<'\n';
*/
}
s.clear();
#define s DONT_USE_THIS
std::vector<int> vals;
for(Event e:evs)
if(e.t==Event::ADD)
vals.push_back(e.n);
std::sort(begin(vals),end(vals));
vals.erase(std::unique(begin(vals),end(vals)),end(vals));
ST t(std::move(vals));
#define vals DONT_USE_THIS
for(Event e:evs){
switch(e.t){
case Event::ADD:
t.set(e.n,true);
break;
case Event::REMOVE:
t.set(e.n,false);
break;
case Event::QUERY:
std::cout<<t.get()<<'\n';
break;
}
}
}
