시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)44221751.515%

문제

크큭.값을..바꿔주마!

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

이 수열은 마을 입구인 $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$줄에 걸쳐 출력한다.

예제 입력 1

9 3
5 9
3 1
5 5

예제 출력 1

54
51
31

예제 입력 2

1000000000000000000 10
2 2
2 1
514284786278117074 386305503
620546740167642922 886374694
109570281517897761 391803195
462938647148434375 949405444
355488278567739598 665574484
469126240319927021 412632134
635995468481642543 663848484
2 2

예제 출력 2

680057396
209783453
209783453
209783453
209783453
209783453
209783453
209783453
209783453
591649086