26331번 - Gold Rush 다국어

문제

After learning about the gold rush in school, your friends have decided to have a gold mining tournament. This one-of-a-kind tournament will be the largest of its kind!

For the tournament, everyone will all line up in a row. Every pair of consecutive people will then face off in a "round" of the tournament. Assuming there are 7 people in the tournament, the first round would look something like this when pairing off: (1, 2) (3, 4) (5, 6) (7).

Notice that when there are an odd number of people in a round, the last person automatically advances to the next round. The remaining players in that round play a best-of-k format where k is an odd number of games. The first person to win ceiling(k/2) games advances to the next round, the other player is eliminated from the tournament, and no more games are played between those players.

For example, let's say players 2, 3, 5, and 7 advance from the first round above. The following round then pairs off in order and the match ups look like this: (2, 3) (5, 7).

The rounds continue in this fashion until a single player remains, the tournament winner!

You would like to know, for a given tournament layout, how many ways the tournament records can play out. Two tournament records are considered different if one of the following conditions is met:

1. The number of games played by a player in the tournament is different.
2. The outcome of the i-th game played by a player is different.

Given the number of players in a tournament and its format (as in best-of-k), determine the number of possible win-loss records.

입력

The input begins with a single positive integer, t, representing the number of tournaments to evaluate. Each of the next t lines contains two integers, n (1 ≤ n ≤ 10¹⁷) and k (1 ≤ k ≤ 10¹⁷), representing the number of players and the best-of-k format, respectively.

출력

For each tournament, output the number of possible win-loss records. As this number may be quite large, output the result modulo 1,000,003.

제한

힌트