26527번 - 당근과 채찍

문제

여행자 $Q$명이 있고, 각 여행자에게는 말이 한 마리씩 있다.

각 여행자는 그의 말을 타고 여행을 떠나기로 한다. 가는 과정에서 말이 배고프지 않게 하기 위한 당근과 앞으로 계속 가게 하기 위한 채찍이 필요하다.

말에게는 '기분' 이라는 수치가 있는데, 0ドル$에서 시작하지만 당근을 먹을 때 기분이 $b$만큼 오르고 채찍으로 때릴 때마다 기분이 $a$만큼 감소한다.

($a,ドル $b$는 서로소인 양의 정수로 말에 따라서 달라질 수 있지만, 여행중에 변하지는 않는다.)

말은 기분이 0ドル$ 미만이 되는 순간 주인을 버리고 달아나기 때문에, 매 순간 말의 기분은 0ドル$ 이상이어야 한다.

각 여행자가 당근 $a$개를 먹이고 채찍으로 $b$번 때려서 여행을 마칠 수 있도록 당근과 채찍을 배열할 때, 가능한 방법의 수를 알려주자!

단, 당근을 먹는 경우와 채찍을 맞는 경우 외에 말의 기분은 변하지 않는다.

입력

첫 번째 줄에 여행자의 수 $Q$가 주어진다. $(1 \leq Q \leq 100,000円)$

다음 $Q$개의 줄에 서로소인 두 정수 $a,ドル $b$가 공백으로 구분되어 주어진다. $(2 \leq a, b \leq 1,000円,000円)$

출력

한 줄에 하나씩 정답을 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

힌트