#include<stdio.h>
//#define Max 200001
#define Max 5
#define Mod 1000000007
typedef struct {
int a;
int b;
double c; // (a-1)/b why double?
}vector;
vector array[Max];
void quickSort(int first, int last)
{
int pivot;
int i;
int j;
vector temp;
if (first < last)
{
pivot = first;
i = first;
j = last;
while (i < j)
{
while (array[i].c <= array[pivot].c && i < last)
{
i++;
}
while (array[j].c > array[pivot].c)
{
j--;
}
if (i < j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
temp = array[pivot];
array[pivot] = array[j];
array[j] = temp;
quickSort(first, j - 1);
quickSort(j + 1, last);
}
}
int main(void)
{
freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);
int T, N;
scanf("%d", &T);
for (int test_case = 1; test_case <= T; test_case++)
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d %d", &array[i].a, &array[i].b);
array[i].c = (double)(array[i].a - 1) / (double)array[i].b;
}
quickSort(0, N - 1);
long long unsigned sum = 1;
for (int i = N - 1; i >= 0; i--)
{
sum = (array[i].a*sum % Mod + array[i].b) % Mod;
}
printf("#%d %d\n", test_case, sum);
}
return 0;
}
댓글