Qnp

시간 제한1.5초메모리 제한256 MB

요약

각 질의마다 주어진 숫자 빈도로 만들 수 있는 정수를 작은 순서로 세었을 때 K번째 값을 10^9 + 7로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

숫자 몇 개가 주어진다. 주어진 숫자를 정확히 한 번씩 모두 사용해서 만들 수 있는 정수 중 $K$ 번째로 작은 수를 $10^9 + 7$ 로 나눈 나머지로 구하라. 질의는 $Q$ 개이며, 각 질의는 숫자 $0$ , $1$ , $\ldots$ , $9$ 의 개수와 정수 $K$ 로 주어진다.

앞자리에 0이 붙은 정수도 센다.

입력

첫 번째 줄에 정수 $Q$ ( $1 \le Q \le 5000$ )가 주어진다.

이어지는 $Q$ 개의 줄에는 각각 정수 11개가 주어진다. 처음 10개는 숫자 $0$ , $1$ , $\ldots$ , $9$ 의 개수이다. 마지막 정수는 $K$ ( $1 \le K \le 10^{12}$ )이다. 각 질의에서 전체 자릿수는 1 이상 $70000$ 이하이다.

출력

$Q$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 질의의 답을 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제1

예제 1

입력

6
1 1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 2
1 1 1 0 0 0 0 0 0 0 5
1 2 0 0 0 0 0 0 0 0 2

예상 출력