골드 러시

학교에서 골드 러시를 배운 친구들이 금광 채굴 토너먼트를 열기로 했다. 이 토너먼트는 같은 종류의 대회 중 가장 큰 규모가 될 것이다.

토너먼트를 위해 모든 참가자가 한 줄로 선다. 그다음 연속한 두 사람이 "라운드"에서 맞붙는다. 참가자가 7명이면 첫 라운드는 (1, 2) (3, 4) (5, 6) (7)로 짝지어진다.

한 라운드의 인원이 홀수이면 마지막 사람은 자동으로 다음 라운드에 진출한다. 나머지 선수들은 k판 선승제로 겨룬다. 여기서 k는 홀수인 경기 수이다. 먼저 $\lceil k/2 \rceil$승을 거둔 선수가 진출하고, 상대는 탈락한다. 두 선수 사이에는 더 이상 경기가 열리지 않는다.

예를 들어 첫 라운드에서 2, 3, 5, 7번 선수가 진출하면 다음 라운드는 순서대로 (2, 3) (5, 7)로 짝지어진다.

라운드는 한 명이 남을 때까지 이런 식으로 계속된다. 마지막에 남은 선수가 토너먼트의 우승자이다.

주어진 토너먼트 형식에서 가능한 승패 기록의 수를 구하라. 두 토너먼트 기록은 다음 중 하나라도 성립하면 서로 다른 것으로 본다.

1. 어떤 선수가 치른 경기 수가 다르다.
2. 어떤 선수가 치른 i번째 경기의 결과가 다르다.

선수 수 n과 k판 선승제의 k가 주어졌을 때, 가능한 승패 기록의 수를 구하라.

첫 줄에 토너먼트의 개수 t가 주어진다. 이어지는 t개의 줄에는 각각 두 정수 n (1 ≤ n ≤ $10^{17}$)과 k (1 ≤ k ≤ $10^{17}$)가 주어지며, 이는 선수 수와 k판 선승제의 k를 뜻한다.

각 토너먼트에 대해 가능한 승패 기록의 수를 1,000,003으로 나눈 나머지를 출력한다.