#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100047;
int mod = 1e9 + 7;
int add(int a, int b)
{
a += b;
if (a >= mod)
a -= mod;
return a;
}
int mult(int a, int b)
{
return 1ll * a * b % mod;
}
int f[N], g[N], h[N];
int main()
{
int n, q;
cin >> n >> q;
f[0] = f[1] = 1;
g[0] = 1;
g[1] = 2;
h[0] = 0;
h[1] = 1;
for (int i = 2; i <= n; i++)
{
f[i] = add(f[i - 1], f[i - 2]);
h[i] = add(h[i - 1], g[i - 1]);
g[i] = add(h[i], add(g[i - 1], add(h[i - 1], g[i - 2])));
}
while (q--)
{
int a, b;
cin >> a >> b;
a = n - a;
b = n - b;
int m = min(a, b);
int d = max(a, b) - m;
cout << add(mult(g[m], f[d]), mult(h[m], f[d - 1])) << '\n';
}
}
