이 멋진 수열에 쿼리를!

피보나치 마을에는 멋진 수열(水列) 이 흐르고 있다. 이 수열은 마을 입구에서 시작해 마을 방향으로 흐른다.

이 수열은 마을 입구인 $0$ 번째 구간으로부터 시작해서 번호가 증가하는 순서대로 연속된 구간으로 나눌 수 있다. 각 수열의 구간에는 특정한 값이 적혀있는데, 이 값은 수열이 흐르는 방향 기준으로, 이전 두 수열 구간에 적혀있던 값의 합으로 계산된다. 특별히 마을 입구인 $0$ 번째 구간에 적힌 값은 $0$이고, $1$ 번째 구간에 적힌 값은 $1$로 고정되어있다.

즉, $i$ 번째 수열 구간에 적힌 값 $F\_i$는 다음과 같이 계산된다.

$F\_i = \begin{cases} 0  & \text{if i = 0} \\\  1  & \text{if i = 1} \\\  F\_{i-1} + F\_{i-2}  & \text{if i > 1} \end{cases}$

당신은 이 피보나치 마을의 $N$ 번째 구간 앞에서 살고 있는 주민이다. 매일같이 자신의 집 앞에 흐르는 수열 구간과, 그 구간에 적혀있는 값을 보면서 마음의 안정을 찾고 있었다.

평화롭게 지내던 어느 날, 사악한 마법사 한별이가 수열에 ‘쿼리마법’ 을 날려서 특정 구간에 적힌 값을 “영구적으로” 바꿔버리는 무시무시한 짓을 하기 시작했다!

아래 그림은 사악한 마법사 한별이가 $5$번째 수열 구간에 값을 $9$로 바꾸는 쿼리마법을 날린 뒤 수열의 모습이다. 쿼리마법에 당한 $5$ 번째 수열 구간은 이전 수열의 값과는 관련 없이 항상 $9$ 라는 값으로 고정되어버리고, $5$ 번째 이후의 수열 구간들은 바뀌어버린 값에 영향을 받아서 같이 값이 바뀌어버리는 것을 확인할 수 있다.

0 일차 (쿼리마법 전)	1 일차

한별이의 만행은 여기서 그치지 않고, 총 $Q$일 동안 매일매일 하루에 한 번씩 쿼리마법을 날리고 있었다! 아래 그림은 한별이가 $3$ 번째 수열 구간의 값을 $1$로 바꾸는 쿼리마법과, $5$ 번째 수열 구간의 값을 $5$로 바꾸는 쿼리마법을 날린 뒤의 모습을 차례로 보여준다. (같은 수열 구간에 쿼리마법이 여러 번 들어오면, 가장 마지막에 날아온 쿼리마법만이 반영된다.)

2 일차	3 일차

자신의 집 앞인 $N$ 번째 수열 구간에 적힌 값이 매일매일 바뀌는 것을 보고 화가 난 당신은 한별이를 고소하기로 했다. 한별이가 쿼리마법을 날린 $Q$일 동안, $N$ 번째 수열 구간에 적힌 값이 어떻게 바뀌었는지 알려주어서 증거물로 제시하자. 값의 크기가 매우 커질 수 있으니 $1\\,000\\,000\\,007$ 로 나눈 나머지를 제시해도 법적인 효력이 적용된다고 가정하자.

첫 번째 줄에는 값을 구하고자 하는 수열 구간의 번호 $N$과 쿼리마법을 날린 일 수 $Q$가 주어진다.  ($3 \leq N \leq 10^{18}$, $1 \leq Q \leq 10^5$)

두 번째 줄부터 $Q+1$ 번째 줄까지 $Q$줄에 걸쳐서 쿼리마법의 정보가 주어진다. $i+1$ 번째 줄에는 두 정수 $A\_i$ $B\_i$ 가 공백을 사이에 두고 주어지며, 이는 $i$ 번째 날에 $A\_i$번 수열 구간의 값을 $B\_i$로 바꾸는 쿼리마법을 날렸음을 의미한다. ($2 \leq A\_i \lt N$, $0 \leq B\_i \lt 1\\,000\\,000\\,007$)

입력으로 주어지는 모든 수는 정수이다.

쿼리마법을 날릴 때마다 $N$ 번째 수열 구간의 값을 $1\\,000\\,000\\,007$ 로 나눈 나머지를 한 줄에 하나씩 총 $Q$줄에 걸쳐 출력한다.