Atcoder ABC129のC問題

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

int main(){
  int64_t N,M; cin>>N>>M;
  
   //i段目まで障害物がなかった時の通りの総和
  vector<int64_t> vec(N+1);
  vec.at(0)=1; vec.at(1)=1;
  for(int i=2; i<=N; i++){
     vec.at(i)=vec.at(i-1)+vec.at(i-2);
     vec.at(i)%=1000000007;
  }
  
  //障害物が2個以上連続しているときは0になる
  vector<int64_t> a(M);
  cin>>a.at(0);
  for(int i=1; i<M; i++) {
     cin>>a.at(i);
     if(a.at(i)==a.at(i-1)+1){cout<<0<<endl;return 0;} 
  }
 
  //障害物間にある段数を上る通りをかけていく
  int64_t ans=vec.at(a.at(0)-1);//一個目の障害物までの通り
  for(int i=1; i<M; i++){
    ans*=vec.at(a.at(i)-a.at(i-1)-2);
    ans%=1000000007;
  }
  ans*=vec.at(N-a.at(M-1)-1);//最後の障害物からN段までの通り
  ans%=1000000007;
  
  cout<<ans<<endl;

}