stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ

#include <bits/stdc++.h>

using namespace std;

bool a[100001]{};

long long memo[100001];

int n, m;



long long climb(int i){

    if(memo[i] > -1) return memo[i];

    long long v = 0;

    if(i == n) return 1;

    if(!a[i+1]) v += climb(i+1);

    v %= 1000000007ll;

    if(i < n-1 && !a[i+2]) v += climb(i+2);

    v %= 1000000007ll;

    memo[i] = v;

    return v;

}



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

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

    cin >> n >> m;

    for(int i = 0, tmp = 0; i < m; i++){

        cin >> tmp;

        a[tmp] = true;

    }

    cout << climb(0);

}


// Faster C++ solution for the same problem (measured speedup: 1.7898399392543465x):
#include <bits/stdc++.h>



#define rev(v) reverse(v.begin(), v.end());

#define mx(v) max_element(v.begin(), v.end());

#define mn(v) min_element(v.begin(), v.end()); 

#define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));

#define mod 1000000007



//ffs = lsb, clz = l0's, ctz = r0's, popcount = 1's 

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++

using namespace std;

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;



int main(){

    fastio();

    ll n,m ; cin >> n >> m;

    ll dp[n + 1];

    for(int i = 0 ; i < n ;++i){

        dp[i] = 0;

    }

    dp[0] = 1;

    dp[1] = 1;

    for(int i = 0; i < m ; ++i){

        int x;  cin >> x;

        dp[x] = -1;

    } 

    

    for(int i = 2 ; i <= n ; ++i){

        if(dp[i] >= 0){

            if(dp[i-1] < 0  && dp[i-2] < 0 ){

                return cout << "0\n" , 0;

            }

            if(dp[i-1] < 0){

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i-2];

            }else if(dp[i-2] < 0){

                dp[i-1] = dp[i-1] % mod;

                dp[i] = dp[i-1];

            }else{

                dp[i-1] = dp[i-1] % mod;

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i - 1] + dp[i - 2];

            }

            dp[i] = dp[i] % mod;

        }

    }



    return cout << dp[n] % mod, 0 ;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<math.h>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

int a[1000000];

long long sum[1000000];

bool vis[1000000];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    memset(vis,0,sizeof(vis));

    memset(a,0,sizeof(a));

    for(int i=1;i<=m;i++)

    {

        scanf("%d",&a[i]);

        vis[a[i]]=1;

    }

    if(vis[1]==1)

        sum[1]=0;

    else

        sum[1]=1;

    if(vis[2]==1)

        sum[2]=0;

    else

        sum[2]=sum[1]+1;

    for(int i=3;i<=n;i++)

    {

        if(vis[i-1]==0&&vis[i-2]==0)

            sum[i]=sum[i-1]%1000000007+sum[i-2]%1000000007;

        if(vis[i-1]==1&&vis[i-2]==0)

            sum[i]=sum[i-2]%1000000007;

        if(vis[i-1]==0&&vis[i-2]==1)

            sum[i]=sum[i-1]%1000000007;

        if(vis[i-1]==1&&vis[i-2]==1)

        {

            sum[n]==0;

            break;

        }

    }

    printf("%lld",sum[n]%1000000007);

        return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.020130082918089x):
#include <bits/stdc++.h>



#define rev(v) reverse(v.begin(), v.end());

#define mx(v) max_element(v.begin(), v.end());

#define mn(v) min_element(v.begin(), v.end()); 

#define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));

#define mod 1000000007



//ffs = lsb, clz = l0's, ctz = r0's, popcount = 1's 

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++

using namespace std;

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;



int main(){

    fastio();

    ll n,m ; cin >> n >> m;

    ll dp[n + 1];

    for(int i = 0 ; i < n ;++i){

        dp[i] = 0;

    }

    dp[0] = 1;

    dp[1] = 1;

    for(int i = 0; i < m ; ++i){

        int x;  cin >> x;

        dp[x] = -1;

    } 

    

    for(int i = 2 ; i <= n ; ++i){

        if(dp[i] >= 0){

            if(dp[i-1] < 0  && dp[i-2] < 0 ){

                return cout << "0\n" , 0;

            }

            if(dp[i-1] < 0){

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i-2];

            }else if(dp[i-2] < 0){

                dp[i-1] = dp[i-1] % mod;

                dp[i] = dp[i-1];

            }else{

                dp[i-1] = dp[i-1] % mod;

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i - 1] + dp[i - 2];

            }

            dp[i] = dp[i] % mod;

        }

    }



    return cout << dp[n] % mod, 0 ;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define all(v) ((v).begin()),((v).end())

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-12, PI = acos(-1);

const int N = 1e6 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



bool la2[N];

int n, m, a;

ll mem[N];



ll dp(int step) {

  if(step == n)

    return 1;

  if(step > n)

    return 0;

  ll& ret = mem[step];

  if(~ret)

    return ret;

  ret = 0;

  if(!la2[step + 1])

    ret = ((ret % MOD) + (dp(step + 1) % MOD)) % MOD;

  if(!la2[step + 2])

    ret = ((ret % MOD) + (dp(step + 2) % MOD)) % MOD;

  return ret;

}



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  cin >> n >> m;

  for (int i = 0; i < m; ++i) {

    cin >> a;

    la2[a] = 1;

  }

  memset(mem, -1, sizeof mem);

  cout << dp(0);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 9.272327519833162x):
#include <bits/stdc++.h>



#define rev(v) reverse(v.begin(), v.end());

#define mx(v) max_element(v.begin(), v.end());

#define mn(v) min_element(v.begin(), v.end()); 

#define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));

#define mod 1000000007



//ffs = lsb, clz = l0's, ctz = r0's, popcount = 1's 

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++

using namespace std;

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;



int main(){

    fastio();

    ll n,m ; cin >> n >> m;

    ll dp[n + 1];

    for(int i = 0 ; i < n ;++i){

        dp[i] = 0;

    }

    dp[0] = 1;

    dp[1] = 1;

    for(int i = 0; i < m ; ++i){

        int x;  cin >> x;

        dp[x] = -1;

    } 

    

    for(int i = 2 ; i <= n ; ++i){

        if(dp[i] >= 0){

            if(dp[i-1] < 0  && dp[i-2] < 0 ){

                return cout << "0\n" , 0;

            }

            if(dp[i-1] < 0){

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i-2];

            }else if(dp[i-2] < 0){

                dp[i-1] = dp[i-1] % mod;

                dp[i] = dp[i-1];

            }else{

                dp[i-1] = dp[i-1] % mod;

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i - 1] + dp[i - 2];

            }

            dp[i] = dp[i] % mod;

        }

    }



    return cout << dp[n] % mod, 0 ;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define in_range(x, y, r, c) (x < r && y < c && x >= 0 && y >= 0)

using namespace std;

const int mod = 1e9+7;

bool no[100100];

int memo[100100];



int ups(int v){

	if (v == 0) return 1;

	if (v < 1) return 0;

	if (no[v]) return 0;

	if (memo[v] != -1) return memo[v];

	return memo[v] = (ups(v-1) + ups(v-2))%mod;

}



int main(){

	int n, m, aux;

	cin >> n >> m;

	memset(no, false, sizeof no);

	memset(memo, -1, sizeof memo);

	for (int i=0; i<m; i++){

		cin >> aux;

		no[aux] = true;

	}

	cout << ups(n) << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.4809498317733096x):
#include <bits/stdc++.h>



#define rev(v) reverse(v.begin(), v.end());

#define mx(v) max_element(v.begin(), v.end());

#define mn(v) min_element(v.begin(), v.end()); 

#define fastio() ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);srand(time(NULL));

#define mod 1000000007



//ffs = lsb, clz = l0's, ctz = r0's, popcount = 1's 

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++

using namespace std;

 //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;



int main(){

    fastio();

    ll n,m ; cin >> n >> m;

    ll dp[n + 1];

    for(int i = 0 ; i < n ;++i){

        dp[i] = 0;

    }

    dp[0] = 1;

    dp[1] = 1;

    for(int i = 0; i < m ; ++i){

        int x;  cin >> x;

        dp[x] = -1;

    } 

    

    for(int i = 2 ; i <= n ; ++i){

        if(dp[i] >= 0){

            if(dp[i-1] < 0  && dp[i-2] < 0 ){

                return cout << "0\n" , 0;

            }

            if(dp[i-1] < 0){

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i-2];

            }else if(dp[i-2] < 0){

                dp[i-1] = dp[i-1] % mod;

                dp[i] = dp[i-1];

            }else{

                dp[i-1] = dp[i-1] % mod;

                dp[i-2] = dp[i-2] % mod;

                dp[i] = dp[i - 1] + dp[i - 2];

            }

            dp[i] = dp[i] % mod;

        }

    }



    return cout << dp[n] % mod, 0 ;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int n,m;

#define mod 1000000007

#define ll long long

vector<int> br;

vector<ll> DP;



ll dp(int i){

  if(i==n) return 1;

  if(i>n) return 0;

  if(br[i]==1) return 0;

  if(DP[i]!=-1) return DP[i];

  return DP[i]=(dp(i+1)+dp(i+2))%mod;

}



int main(){

  scanf("%d %d",&n,&m);

  br.resize(n+1,0);

  for(int i=0;i<m;i++){

    int a;

    scanf("%d",&a);

    br[a]=1;

  }



  DP.resize(n+1,-1);

  printf("%lld\n",dp(0));



  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.151367168989901x):
#include <stdio.h>

long long mod=1e9+7;

long long vis[100005],a[100005]={1,1,2};

int main()

{

    long long i,x,n,k;

    scanf("%lld%lld",&n,&k);

    for(i=1; i<=k; i++)

    {

        scanf("%lld",&x);

        vis[x]=1;

    }

    if(vis[1]) a[1]=0;

    for(i=2; i<=n; i++)

    {

        if(vis[i]) a[i]=0;

        else a[i]=(a[i-1]%mod+a[i-2]%mod)%mod;

    }

    printf("%lld\n",a[n]);

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<math.h>

using namespace std;

int n,m;

int broken[100005];

int memo[100005];

int o = (int)1e9+7;

int dp(int idx){

//	cout<<idx<<"\n";

	if(idx == n) return 1;

	if(memo[idx]!=-1) return memo[idx];

	int one = 0, two = 0;

	if(broken[idx+1]!=1){

		one = dp(idx+1);

	}

	if(broken[idx+2]!=1 && idx+2<=n){

		two = dp(idx+2);

	}

	return memo[idx] = ((one%o) +(two%o))%o;

}

int main(){

	int a;

	cin>>n>>m;

	for(int i = 0;i<m;i++){

		cin>>a;

		broken[a] = 1;

	}

	for(int i = 0;i<=n;i++)memo[i] = -1;

	cout<<dp(0)%o<<"\n";

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.203448182946226x):
#include <stdio.h>

long long mod=1e9+7;

long long vis[100005],a[100005]={1,1,2};

int main()

{

    long long i,x,n,k;

    scanf("%lld%lld",&n,&k);

    for(i=1; i<=k; i++)

    {

        scanf("%lld",&x);

        vis[x]=1;

    }

    if(vis[1]) a[1]=0;

    for(i=2; i<=n; i++)

    {

        if(vis[i]) a[i]=0;

        else a[i]=(a[i-1]%mod+a[i-2]%mod)%mod;

    }

    printf("%lld\n",a[n]);

    return 0;

}
// Slower C++ solution:
//

// Created by Mahmoud Rashad on 11/27/19.

//



#include <bits/stdc++.h>





using namespace std;



typedef vector<int> vi;

typedef pair<int, int> ii;

typedef vector<pair<ii, ii>> vii;



const int Mod = (int)1e9 + 7;



int mul(int a, int b) {

    return 1LL * a * b % Mod;

}



const int MAXN = 100005;

int n;

int memo[MAXN];

set<int> st;

int count(int step) {

    if (step == n)

        return 1;

    if (step > n)

        return 0;

    if (st.find(step) != st.end())

        return 0;

    int &ret = memo[step];

    if (~ret)

        return ret;

    ret = 0;

    ret += count(step + 1);

    ret %= Mod;

    ret += count(step + 2);

    ret %= Mod;

    return ret;

}



int main() {

#ifndef ONLINE_JUDGE

//    freopen("input.txt", "r", stdin);

//    freopen("output.out", "w", stdout);

#endif

    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;



    int m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {

        int x;

        cin >> x;

        st.insert(x);

    }



    memset(memo, -1, sizeof memo);

    cout << count(0) << '\n';

}

// Faster C++ solution for the same problem (measured speedup: 1.3988438756191255x):
#include <bits/stdc++.h>



using namespace std;



const int N = 1e5 + 5 , MOD = 1e9 + 7;

int dp[N];

bool bad[N];



int main() {

    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);



    int n , m;

    cin >> n >> m;



    for (int i = 0 ;i < m ;i++) {

        int x;

        cin >> x;

        bad[x] = 1;

    }



    dp[0] = !bad[0];

    for (int i = 1 ;i <= n ;i++) if (!bad[i]) {

        if (i > 0 && !bad[i - 1])

            dp[i] = (dp[i] + dp[i - 1]) % MOD;

        if (i > 1 && !bad[i - 2])

            dp[i] = (dp[i] + dp[i - 2]) % MOD;

    }



    cout << dp[n];

}
// Slower C++ solution:
//

// Created by Mahmoud Rashad on 11/27/19.

//



#include <bits/stdc++.h>





using namespace std;



typedef vector<int> vi;

typedef pair<int, int> ii;

typedef vector<pair<ii, ii>> vii;



const int Mod = (int)1e9 + 7;



int mul(int a, int b) {

    return 1LL * a * b % Mod;

}



const int MAXN = 100005;

int n;

int memo[MAXN];

set<int> st;

int count(int step) {

    if (step == n)

        return 1;

    if (step > n)

        return 0;

    if (st.find(step) != st.end())

        return 0;

    int &ret = memo[step];

    if (~ret)

        return ret;

    ret = 0;

    ret += count(step + 1);

    ret %= Mod;

    ret += count(step + 2);

    ret %= Mod;

    return ret;

}



int main() {

#ifndef ONLINE_JUDGE

//    freopen("input.txt", "r", stdin);

//    freopen("output.out", "w", stdout);

#endif

    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;



    int m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {

        int x;

        cin >> x;

        st.insert(x);

    }



    memset(memo, -1, sizeof memo);

    cout << count(0) << '\n';

}

// Faster C++ solution for the same problem (measured speedup: 1.4166218024425843x):


#include <iostream>

#include <algorithm>



using namespace std;



#define MOD 1000000007



int main() {

    int N, M; cin >> N >> M; int A, visited[N+1] = {}; long long fib[N+1] = {1};

    for (int i = 1; i <= M; i++) cin >> A, visited[A] = 1;

    if (not visited[1]) fib[1] = 1;

    for (int i = 2; i <= N; i++) if (not visited[i]) fib[i] = (fib[i-1]+fib[i-2]) % MOD;

    cout << fib[N] << endl;

    return 0;

}
// Slower C++ solution:
//

// Created by Mahmoud Rashad on 11/27/19.

//



#include <bits/stdc++.h>





using namespace std;



typedef vector<int> vi;

typedef pair<int, int> ii;

typedef vector<pair<ii, ii>> vii;



const int Mod = (int)1e9 + 7;



int mul(int a, int b) {

    return 1LL * a * b % Mod;

}



const int MAXN = 100005;

int n;

int memo[MAXN];

set<int> st;

int count(int step) {

    if (step == n)

        return 1;

    if (step > n)

        return 0;

    if (st.find(step) != st.end())

        return 0;

    int &ret = memo[step];

    if (~ret)

        return ret;

    ret = 0;

    ret += count(step + 1);

    ret %= Mod;

    ret += count(step + 2);

    ret %= Mod;

    return ret;

}



int main() {

#ifndef ONLINE_JUDGE

//    freopen("input.txt", "r", stdin);

//    freopen("output.out", "w", stdout);

#endif

    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;



    int m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {

        int x;

        cin >> x;

        st.insert(x);

    }



    memset(memo, -1, sizeof memo);

    cout << count(0) << '\n';

}

// Faster C++ solution for the same problem (measured speedup: 1.384745254962099x):
#include <bits/stdc++.h>



#define ll long long

#define ii pair<int, int>

#define vi vector<int>

#define vl vector<ll>

#define pb push_back

#define eb emplace_back

#define mp make_pair

#define mt make_tuple

#define ff first

#define ss second

#define pi 3.14159265

#define oo 1000000007

#define loo 10000000000000007



#define prime 1000000007



#define W(x) cerr << "\033[31m" << #x << " = " << x << "\033[0m" << "\n";

using namespace std;



ll fib[100100];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    fib[0] = 1;

    fib[1] = 1;

    for (int i = 2; i <= n; ++i){

        fib[i] = (fib[i-1]+fib[i-2])%prime;

        //W(fib[i])

    }

    vi v {0};

    for (int i = 0; i < m; ++i){

        int x; cin >> x;

        v.pb(x);

    }

    v.pb(n+1);

    sort(v.begin(), v.end());

    ll sum = 1;

    for (int i = 1; i < (int)v.size(); ++i){

        //if(i == 1 && v[i] == 1) continue;

        //if(v[i] == n && v[i-1] == v[i]-1) continue;

        if(v[i]-v[i-1]-1 < 0) {

            sum = 0;

            break;

        }

        if(i == 1) {

            sum *= fib[v[i]-v[i-1]-1];

            //W(fib[v[i]-v[i-1]-1])

        }

        else{ 

            sum *= fib[v[i]-v[i-1]-2];

            //W(fib[v[i]-v[i-1]-2])

        }

        //W(sum)

        sum%=prime;

        //W(sum)

    }

    cout << sum << endl;



    return 0;

}
// Slower C++ solution:
//

// Created by Mahmoud Rashad on 11/27/19.

//



#include <bits/stdc++.h>





using namespace std;



typedef vector<int> vi;

typedef pair<int, int> ii;

typedef vector<pair<ii, ii>> vii;



const int Mod = (int)1e9 + 7;



int mul(int a, int b) {

    return 1LL * a * b % Mod;

}



const int MAXN = 100005;

int n;

int memo[MAXN];

set<int> st;

int count(int step) {

    if (step == n)

        return 1;

    if (step > n)

        return 0;

    if (st.find(step) != st.end())

        return 0;

    int &ret = memo[step];

    if (~ret)

        return ret;

    ret = 0;

    ret += count(step + 1);

    ret %= Mod;

    ret += count(step + 2);

    ret %= Mod;

    return ret;

}



int main() {

#ifndef ONLINE_JUDGE

//    freopen("input.txt", "r", stdin);

//    freopen("output.out", "w", stdout);

#endif

    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(10), cout << fixed;



    int m;

    cin >> n >> m;

    for (int i = 0; i < m; ++i) {

        int x;

        cin >> x;

        st.insert(x);

    }



    memset(memo, -1, sizeof memo);

    cout << count(0) << '\n';

}

// Faster C++ solution for the same problem (measured speedup: 1.398830262813225x):
#include <bits/stdc++.h>



#define ll long long

#define EPS (ll)1e-9

#define N (ll)(2*1e5)

#define M (ll)(1e9+7)



using namespace std;



bitset<100010> trap;

ll dp[N];



ll solve(ll n) {

    dp[0] = 1;

    dp[1] = trap[1] ? 0 : 1;



    for(ll i = 2; i <= n; i++) {

        if(trap[i])

            dp[i] = 0;

        else 

            dp[i] = (dp[i-1] + dp[i-2])%M;

    }

    return dp[n]%M;

}





int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    srand(time(NULL));



    ll n, m, pos;



    cin >> n >> m;



    for(ll i = 0; i < m; i++) {

        cin >> pos;

        trap[pos] = true;

    }

    cout << solve(n) << endl;

    

    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;



const int MOD = 1000000007;

bool is_safe[100010];

int dp[100010];



int rec(int i) {

    if(dp[i] != -1) return dp[i];

    if(i == 0) return 1;

    int res = 0;

    if(is_safe[i-1]) res += rec(i-1);

    if(is_safe[i-2]) res += rec(i-2);

    return dp[i] = res % MOD;

}



int main() {

    int N, M; cin >> N >> M;

    for(int i = 0; i < 100010; ++i) {

        is_safe[i] = true;

        dp[i] = -1;

    }

    

    for(int i = 0; i < M; ++i) {

        int a; cin >> a;

        is_safe[a] = false;

    }

    

    cout << rec(N) << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.4979240017895716x):
#include <iostream>

#include <vector>

using namespace std;



const int MOD = 1000000007;



int main() {

    int N, M; cin >> N >> M;

    vector<bool> is_safe(N+1, true);

    for(int i = 0; i < M; ++i) {

        int a; cin >> a;

        is_safe[a] = false;

    }

    

    vector<int> dp(N+2, 0);

    dp[0] = 1;

    for(int i = 0; i < N; ++i) {

        if(is_safe[i+1] && is_safe[i]) dp[i+1] += dp[i], dp[i+1] %= MOD;

        if(is_safe[i+2] && is_safe[i]) dp[i+2] += dp[i], dp[i+2] %= MOD;

    }

    

    cout << dp[N] << endl;

}
// Slower C++ solution:
#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

int lt,ls,i,j,tt,ans=0x7fffffff;

char s[1010],t[1010];

int main () {

	scanf ("%s%s",s+1,t+1);

	ls=strlen (s+1);

	lt=strlen (t+1); 

	for (i=1;i<=ls-lt+1;i++) {

        tt=0;

		for (j=i;j<=i+lt-1;j++) {

			if (s[j]!=t[j-i+1]) {

				tt++;

			}

		}

		ans=min (tt,ans); 

	}

	printf ("%d\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.193384933706228x):
#include <cstdio>

#include <cstring>

#define min(a,b) ((a)<(b)?(a):(b))

char s[1003],t[1003];

int lens,lent,ans=1<<30,sum;

int main(){

    scanf("%s%s",s,t);

    lens=strlen(s),lent=strlen(t);

    for(int i=0;i<lens-lent+1;i++){

        sum=0;

        for(int j=0;j<lent;j++) if(s[i+j]!=t[j]) ++sum;

        ans=min(ans,sum);

    }

    printf("%d\n",ans);

    return 0;

}