#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  long long int n, k;
  long long int mod = 1000000007;
  cin >> n >> k;
  long long int dp[n + 1];
  dp[0] = 1;
  bool ans = true;
  priority_queue<long long int, vector<long long int>, greater<long long int> >
      p;
  for (long long int i = 0; i < k; i++) {
    long long int a;
    cin >> a;
    p.push(a);
  }
  for (long long int i = 1; i <= n; i++) {
    if (i == p.top()) {
      cout << p.top() << endl;
      dp[p.top()] = 0;
      p.pop();
    } else {
      dp[i] = ((dp[i - 1] % mod) + (dp[i - 2] % mod)) % mod;
    }
    cout << (i) << " " << dp[i] << endl;
  }
  cout << dp[n] << endl;
  return 0;
}
