시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB130413939.000%

문제

일자로 된 지하철 선로에 $N$개의 조명이 설치되어 있다. 이 조명들은 모두 솔빛공업에서 만들었다.

솔빛공업의 조명은 고유한 등급과 확산도를 가진다. $i$번째 조명은 선로 위의 위치 $p_i$에 설치되어 있고, 등급은 $l_i$, 확산도는 $d_i$이다. $p_i, l_i, d_i$는 모두 정수이며, 모든 $l_i$는 서로 다르다.

조명이 설치되기 전 선로 위 모든 점의 초기 밝기는 $0$이고, 여기에 설치된 조명이 주변의 정수 지점을 비춰 밝기를 올린다. 선로 위의 정수 위치 $x$에서 $$L_{i,x}= l_i - \left \lfloor \frac{|p_i-x|}{d_i} \right \rfloor \geq 0$$을 만족하면, 위치 $x$의 밝기는 $i$번째 조명에 의해 $A^{L_{i,x}}$만큼 증가한다. 여기서 $A$는 솔빛공업의 모든 조명이 공유하는 밝기 상수로, $\boldsymbol{A \geq N}$이다.

명준이는 지하철을 타면 얼마나 눈부실지 궁금해졌다. 명준이를 위해 지하철 선로에서 최대 밝기와 최대 밝기가 나타나는 위치를 구해주자.

입력

첫 번째 줄에 설치된 조명의 개수 $N$과 밝기 상수 $A$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N+1$번째 줄까지 $i + 1$번째 줄에 각 조명을 표현하는 세 정수 $p_i, l_i, d_i$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 최대 밝기를 $10^9+7$로 나눈 나머지를 출력하라.

두 번째 줄에 최대 밝기를 가지는 정수 위치를 출력하라. 최대 밝기를 가지는 정수 위치가 여러 개 존재한다면, 그중 아무거나 출력하라.

제한

  • $1 \le N \le 10^4$
  • $N \le A \le 10^9$
  • $-10^9 \le p_i \le 10^9$
  • $0 \le l_i \le 10^9$ $(1 \le i \le N)$
  • $l_i \neq l_j$ $(1 \le i < j \le N)$
  • $1 \le d_i \le 100$ $(1 \le i \le N)$

서브태스크

번호배점제한
116

$N\le15,\ l_i \le15,\ |p_i| \le 10^6,\ A \le 15$

224

$d_i = 1$

360

추가 제약 조건 없음

예제 입력 1

1 2
0 1 1

예제 출력 1

2
0

예제 입력 2

3 3
0 2 1
1 1 1
-1 0 1

예제 출력 2

10
0

예제 입력 3

2 5
-2 1 1
3 0 1

예제 출력 3

5
-2

예제 입력 4

3 4
2 3 2
3 1 2
4 2 1

예제 출력 4

72
3

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.