#2431 학습 네트워크

10  1 s   128 MB  

Description

최근 들어 기계 학습에 관해 관심을 가지기 시작한 아영이는 오랜 연구 끝에 외부 자극에 대해서 자극의 의미를 해석할 수 있는 새로운 네트워크를 고안해냈습니다.
아영이는 이를 학습 네트워크라고 이름 지었습니다. 학습네트워크는 Figure 1 같이 표현할 수 있습니다.
 

 

학습 네트워크는 일종의 블랙박스여서, 입력값들이 주어지면 이를 네트워크의 특성에 따라 처리해 정수의 결과값을 생성합니다.

학습 네트워크는 정점과 방향성이 있는 간선으로 구성된 그래프로 표현되며, 편의상 각 정점은 1번부터 N 번까지의 번호를 부여합니다.
각 정점에는 임의의 값이 부여되는데, 이 값은 자신을 향하는 간선들을 통해 흘러들어오는 값들의 총합으로 정의됩니다. 더불어 각 정점은 자신의 값을 자신에게서 나가는 간선들에게 각각 흘려보내 다른 정점으로 전달하게 됩니다. 학습 네트워크에서 순환하는 경로는 존재하지 않으며, 임의의 두 개의 정점을 연결하는 간선은 최대 1개 존재할 수 있습니다.
 
학습 네트워크의 정점 중 S 개의 정점은 입력 정점이라 정의되며, 해당 정점들은 자신에게 할당된 입력값 또한 흘러들어온 값으로 인식합니다. 또, N 번 정점은 결과 정점이라고 정의하며 결과 정점에 할당된 값에 따라 외부 자극의 종류를 분류하게 됩니다.
아영이는 가능한 모든 외부 자극의 종류에 대해 결과 정점의 값이 K 이상이 되어 강한 외부 자극을 발생시키는 입력의 경우의 수를 알고 싶어졌습니다. 
불행히도 아영이는 훌륭한 생물학도이지만, 아직 모든 경우의 수를 셈하는 문제에는 익숙하지 않습니다.
이러한 아영이를 위해서 모든 경우의 수를 세는 프로그램을 작성해줍시다!
 

Input

한 줄에 입력되는 인접한 숫자 사이는 공백으로 구분됩니다.

Output

각 테스트 케이스에 대해 한 줄에 가능한 경우의 수를 출력합니다

Sample Input

Sample Output

3
4 4 7
1 2
1 3
2 4
3 4
2
1 3 1 2 3
2 2 4 5
2 0 4
1
1 3 1 2 3
3 2 5
1 2
2 3
2
1 1 2
2 1 3
5
0
1

Source

shake! 2015 본선