MAX = 100047
MOD = 10 ** 9 + 7
def add(a, b):
a += b
if a >= MOD:
a -= MOD
return a
def mult(a, b):
return a * b % MOD
n, q = map(int, input().split())
f = [0] * MAX
g = [0] * MAX
h = [0] * MAX
f[0] = f[1] = 1
g[0] = 1
g[1] = 2
h[0] = 0
h[1] = 1
for i in range(2, n + 1):
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])))
for i in range(q):
a, b = map(int, input().split())
a = n - a
b = n - b
m = min(a, b)
d = max(a, b) - m
print(add(mult(g[m], f[d]), mult(h[m], f[d - 1])))
