고전적인 개수 세기 문제
시간 제한2초메모리 제한1024 MB
각 심사위원이 v개 문제에 투표한 뒤 상위 p개가 될 수 있는 문제 집합의 개수를 998244353으로 나눈 나머지로 구합니다.
문제
이번 대회를 위해 개의 문제가 제안되었다. 번 문제의 초기 점수는 정수 점이다.
명의 심사위원이 마음에 드는 문제에 투표한다. 각 심사위원은 다른 심사위원과 독립적으로 정확히 개의 문제를 고르고, 고른 문제마다 점수를 씩 올린다.
명의 심사위원이 모두 투표를 마치면 문제를 점수의 내림차순으로 정렬하고, 앞의 개 문제를 문제집에 넣는다. 여기서 는 이상 이하의 어떤 값이든 될 수 있다. 점수가 같은 문제의 순서는 임의로 정할 수 있으며, 이 순서는 대회 감독이 정한다.
가능한 문제집은 몇 가지인가? 이 수를 으로 나눈 나머지를 출력하라. 한쪽 문제집에만 속한 문제가 하나라도 있으면 두 문제집은 서로 다른 것으로 본다.
입력
각 테스트 케이스는 여러 개의 테스트 케이스로 구성된다. 첫 줄에 테스트 케이스의 개수 ()가 주어진다. 각 테스트 케이스의 설명이 이어진다.
각 테스트 케이스의 첫 줄에는 문제의 개수 , 심사위원의 수 , 각 심사위원이 고르는 문제의 수 가 주어진다 (; ; ).
둘째 줄에는 문제들의 초기 점수 이 주어진다 ().
모든 테스트 케이스에 대한 의 합은 을 넘지 않는다.
출력
각 테스트 케이스마다 가능한 문제집의 수를 으로 나눈 나머지를 출력한다.
힌트
첫 번째 테스트 케이스에서 가능한 문제집은 , , , , 이다.
두 번째 테스트 케이스에서 가능한 문제집은 , , , , , 이다.
세 번째 테스트 케이스에서는 공집합이 아닌 문제들의 부분집합이 모두 가능한 문제집이다.