25621번 - 이상한 프로그래밍 언어

키파는 새로운 프로그래밍 언어를 만들었습니다. 이 프로그래밍 언어의 변수는 정확히 하나인데 지금부터 K라고 부르겠습니다. 최초에 K는 입력 값으로 설정됩니다.

이 변수에 시행하는 연산은 다음과 같이 정의됩니다.

• +x: K에 x를 더합니다.
• -x: K에서 x를 뺍니다. 단, 이 프로그래밍 언어는 음이 아닌 정수만 처리할 수 있어서, 만일 K ≤ x이면 K는 0이 됩니다.
• *x: K에 x를 곱합니다.

이 프로그래밍 언어의 특이한 점은 각 줄에 두 개의 연산을 받는다는 점입니다. 실행은 다음과 같은 식으로 이루어집니다.

1. 수 하나를 입력받고, K를 입력받은 값으로 설정합니다.
2. 각 줄에 있는 두 개의 연산 중 하나를 아무렇게나 선택합니다.
3. 각 줄에 있는 연산을 K에 순서대로 적용합니다.
4. 마지막 연산까지 시행한 후 K의 값을 출력합니다.

키파는 N개의 줄로 구성된 프로그램을 짰습니다. 이 프로그램의 가능한 출력 중 가장 큰 값은 무엇일까요?

첫째 줄에 N과 입력값 K₀가 공백을 사이에 두고 주어집니다. (1 ≤ N ≤ 300 000, 0 ≤ K₀ ≤ 10⁹)

둘째 줄부터 N개의 줄에 프로그램이 주어집니다. 구체적으로, (i + 1)번째 줄에 위에서 설명한 형식으로 된 연산 두 개가 공백을 사이에 두고 주어집니다.

연산에 쓰이는 수 x는 모두 0 이상 10⁹ 이하의 정수입니다.

첫째 줄에 가능한 출력 중 가장 큰 값을 10⁹ + 7로 나눈 나머지를 출력합니다.

가능한 출력을 10⁹ + 7로 나눈 나머지를 최대화하는 것이 아님에 주의하세요.

가능한 실행 방법 중 하나는 다음과 같습니다.

1. K₀ = 15를 입력받고, K를 그 값으로 설정합니다. 따라서 K := K₀ = 15가 됩니다.
2. 각 줄에서 연산을 하나씩 고르는데, 구체적으로 첫째 줄에서는 +10, 둘째 줄에서는 -20, 셋째 줄에서는 *20을 고릅니다.
3. 각 연산을 순서대로 시행하면, 첫째 줄 시행 이후 K := 15 + 10 = 25, 둘째 줄 시행 이후 K := 25 − 20 = 5, 셋째 줄 시행 이후 K := 5 × 20 = 100이 됩니다.
4. 100을 출력합니다.

이렇게 실행하는 방법이 다른 방법에 비해 가장 큰 값을 출력함을 알 수 있습니다. 가장 큰 출력값인 100을 10⁹ + 7로 나눈 나머지인 100을 출력합니다.