시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 112 | 45 | 27 | 38.028% |
피보나치 마을에는 멋진 수열(水列) 이 흐르고 있다. 이 수열은 마을 입구에서 시작해 마을 방향으로 흐른다.
이 수열은 마을 입구인 $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$줄에 걸쳐 출력한다.
9 3 5 9 3 1 5 5
54 51 31
1000000000000000000 10 2 2 2 1 514284786278117074 386305503 620546740167642922 886374694 109570281517897761 391803195 462938647148434375 949405444 355488278567739598 665574484 469126240319927021 412632134 635995468481642543 663848484 2 2
680057396 209783453 209783453 209783453 209783453 209783453 209783453 209783453 209783453 591649086