26165번 - 용암 점프 2

경기과학고등학교 학습실에는 때때로 용암이 찬다. 이 용암 바닥에 1부터 N까지의 정수 번호가 각각 매겨진 N 개의 발판이 떠 있다. i번 발판의 위치는 하나의 정수 a_i로 표현되며, 각 발판의 위치는 서로 다르다. 다시 말해, 1 ≤ i < j ≤ N인 두 정수 i, j에 대하여 a_i ≠ a_j이다. 용암 바닥은 밟을 수 없으며, 발판만 밟을 수 있다. 안타깝게도, 한 번 밟은 발판은 발판에서 발을 떼는 순간 용암 바닥 아래로 영원히 가라앉아 다시 밟을 수 없게 된다.

정후는 친구 이환이가 각 발판에서 시작하여 0 회 이상의 점프를 통해 마지막에 밟고 있는 하나의 발판을 제외한 모든 발판을 가라앉게 할 수 있는 경우의 수가 궁금하다. 하지만 운동 과잉인 이환이는 한 번 x만큼의 거리를 뛴 이후에는 2x 이상만큼의 거리만을 뛸 수 있다. 처음에는 어느 거리를 뛰어도 상관없다.

i번 발판에서 j번 발판으로 뛰는 거리는 |a_i-a_j|와 같다. 발판이 가라앉는 순서가 서로 다르다면 서로 다른 경우의 수이다. 밟지 않은 발판은 가라앉지 않는다. 발판의 이동은 누적된다.

정후의 궁금증을 해결해 주자.

첫째 줄에 발판의 수와 쿼리의 개수를 나타내는 두 정수 N, Q가 주어진다.

둘째 줄에 발판의 위치를 나타내는 N 개의 정수가 공백으로 구분되어 주어진다. 이중 i째 정수는 i번 발판의 위치 ai를 나타낸다.

다음 Q 개의 줄에 발판의 이동을 나타내는 두 정수가 각각 주어진다. 이중 i째 줄의 두 정수 b_i와 c_i는 차례로 b_i째 발판이 위치 c_i로 이동함을 나타낸다.

첫째 줄에 초기에 이환이가 각 발판에서 시작하여 0 회 이상의 점프를 통해 마지막에 밟고 있는 하나의 발판을 제외한 모든 발판을 가라앉게 할 수 있는 경우의 수의 합을 10⁹ + 7로 나눈 나머지를 나타내는 하나의 정수를 출력한다.

다음 Q 개의 줄에 걸쳐 i 번째 줄에는 발판의 i 번째 이동 이후 이환이가 각 발판에서 시작하여 0 회 이상의 점프를 통해 마지막에 밟고 있는 하나의 발판을 제외한 모든 발판을 가라앉게 할 수 있는 경우의 수의 합을 10⁹ + 7로 나눈 나머지를 나타내는 하나의 정수를 출력한다.

• 1 ≤ N ≤ 40,000
• 0 ≤ Q ≤ 40,000
• -10¹⁸ ≤ a_i, c_i ≤ 10¹⁸
• 1 ≤ b_i ≤ N
• 초기와 매 쿼리 이후 발판의 위치는 서로 다르다.
• 주어지는 모든 수는 정수이다.