패트릭의 삼각형

패트릭은 유명해지고 싶었던 무명 수학자다. 그는 블레즈 파스칼이 자신의 삼각형인 파스칼의 삼각형으로 유명해졌다는 이야기를 들었다.

패트릭도 자신만의 삼각형인 패트릭의 삼각형을 만들면 유명해질지도 모른다고 생각했다. 오랜 고민 끝에 그는 다음과 같은 방법으로 삼각형을 만들었다.

1. 삼각형의 왼쪽 변과 오른쪽 변을 따라 삼각수 $1,3,6,10,15,21,\ldots$ 을 적는다.

2. 파스칼의 삼각형을 만드는 방식과 같이 안쪽을 채운다. 각 수는 바로 왼쪽 위의 수와 바로 오른쪽 위의 수를 더해 구한다.

패트릭은 삼각형을 유명하게 만들려면 다른 누구도 먼저 발명하지 않았어야 한다는 것을 알고 있었다. 그래서 정수 수열 백과사전(On-Line Encyclopedia of Integer Sequences, OEIS.org)을 검색했고, 다행히 그의 삼각형은 목록에 없었다.

이제 남은 일은 삼각형을 OEIS에 올리는 것이었다. 패트릭은 손으로 처음 $10^6$ 행까지 계산했다. 올리기 전에 계산에 오류가 없는지 확인하고 싶었다. 그의 계산이 맞는지 확인하는 일을 도와줄 수 있겠는가?

처음 6개의 삼각수. Wikimedia Commons, CC BY-SA 3.0.

첫 줄에 정수 $Q$ ($1 \leq Q \leq 2 \cdot 10^5$)가 주어진다. 이는 질의의 개수이다. 다음 $Q$개의 줄에는 공백으로 구분된 세 정수 $N$, $K$, $X$ ($1 \leq K \leq N \leq 10^6$, $0 \leq X < 10^9+7$)가 주어진다. 여기서 $X$는 패트릭이 계산한 값으로, 패트릭의 삼각형에서 $N$행의 $K$번째 수를 $10^9+7$로 나눈 나머지이다. 패트릭은 $X$가 맞는지 알고 싶어 한다.

각 질의에 대해, 패트릭의 삼각형에서 $N$행의 $K$번째 수가 $X$를 $10^9+7$로 나눈 나머지와 같으면 Correct를, 아니면 Incorrect를 한 줄에 출력한다.