등수
시간 제한3초메모리 제한1024 MB
N명이 참가한 대회에서 특정 참가자가 정확히 K등이 되는 서로 다른 최종 등수 배치의 수를 구한다. 동점은 같은 등수로 처리한다.
문제
소프트웨어에 진심인 LG전자는 개발자들이 문제 해결 능력을 겨루고 지적 즐거움을 누릴 수 있도록 2012년부터 매년 LG Code Jam을 개최하고 있다.
LG Code Jam에서 우수한 성적을 거둔 개발자는 코딩 전문가로 선발되어 비즈니스 문제 해결 및 개발자 교육과 같은 다양한 분야에 기여하고 있다.
특히, 신입 개발자라도 뛰어난 실력을 갖추면 전문가 타이틀을 획득할 수 있다.
이와 함께 LG전자는 2024년 LG 대학생 프로그래밍 경진대회를 개최하여 실력 있는 학생들에게도 지적 즐거움을 제공할 예정이다.
운 좋은 금성이는 2024년 LG 대학생 프로그래밍 경진대회에 참가하여 등을 기록하는 꿈을 꾸고 있다. 이번 LG 대학생 프로그래밍 경진대회에는 총 명이 참가할 것이다.
금성이는 자신이 등을 기록했을 때 나올 수 있는 서로 다른 대회 결과의 경우의 수를 구하고 싶다. 두 대회의 결과가 서로 다르다는 것은 두 대회에서의 등수가 다른 참가자가 1명 이상 존재한다는 뜻이다.
단, 동점을 기록한 사람들은 같은 등수가 된다. 예를 들어, 공동 2등이 3명일 수 있고, 이 경우 다음 등수는 5등이 된다.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다.
다음 줄부터 각 테스트 케이스마다 과 의 값이 한 줄에 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 문제의 정답을 로 나눈 나머지를 한 줄에 출력한다.