시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB343974720.172%

문제

임베디드 개발자인 진우는 방구석에서 데이터 시트만 보며 허무한 학창 시절을 보냈다. 하지만 주변 친구들의 수많은 구원의 손길 끝에, 소개팅에서 만난 한콩이와 장거리 연애를 시작했다! 모태솔로였던 진우의 고백은 마치 러블리즈의 곡 Close To You가 생각나는 장면이었다.

진우는 두근거리는 첫 데이트를 앞두고 있다. 진우는 이번 첫 데이트를 통해 한콩이에게 섬세하고 꼼꼼한 남자친구의 이미지를 각인시키려고 한다. 단순무식한 진우는 약속된 시간 동안 돌아다닐 수 있는 데이트 동선의 모든 경우의 수를 시뮬레이션해서 여러 상황을 대비하기로 결정했다.

바야흐로 언택트 시대, 진우는 차량을 렌트해 한콩이와 드라이브를 하기로 했다. 이를 위해 진우는 미리 지도에 N개의 동네를 표시해두었다. 그리고 한콩이를 데리러 가기 좋은 동네의 집합 P와 한콩이를 바래다 주기 좋은 동네 집합 Q를 정했다. 참고로, 집합 P와 집합 Q의 교집합에 속하는 동네가 존재할 수 있다.

진우의 지도는 그래프 구조로 그려져 있다. 동네를 각 정점으로 하고 양방향 간선으로 도로를 표현한다. 도로는 항상 서로 다른 두 동네를 이어주며, 도로를 통해 이동하는 시간은 항상 1이라고 가정한다. 진우의 드라이브 규칙은 다음과 같다.

  • P에 속한 동네 중 한 곳에서 출발하여 Q에 속한 동네 중 한 곳에서 드라이브를 마쳐야 한다.
  • 진우는 드라이브 동안 도로를 최소 1번, 최대 K번 이용할 수 있다.
  • 드라이브 동안 멈추지 않고 도로를 통해 이동해야한다. 한콩이가 지루해 할 수 있다.
  • 이동 과정에서 같은 동네나 도로를 여러 번 방문하는 것은 허용된다.
  • 위 규칙을 하나라도 위반하는 경우 드라이브 경로로 고려하지 않는다.

뼛속까지 공대생인 진우는 위의 규칙을 칼같이 지키며 드라이브를 하려고 한다. 진우가 [1, K]의 시간 동안 드라이브를 할 수 있을 때, 발생할 수 있는 드라이브 경로의 수는 몇 가지인지 계산하는 프로그램을 작성하시오. 

경우의 수가 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫 번째 줄에는 세 개의 자연수 N, M, K가 공백으로 구분되어 주어진다.

  • N은 동네의 수를 나타내는 2 이상 100 이하의 자연수다
  • M은 도로의 수를 나타내는 1 이상 20,000 이하의 자연수다
  • K는 최대로 드라이브를 할 수 있는 시간을 나타내는 1 이상 1,000,000 이하의 자연수다.

이후 총 M개의 간선의 정보가 한 줄에 하나씩 주어진다

  • 도로의 정보는 U V 형식으로 주어진다. (단, U ≠  V )
  • 서로 다른 두 동네간에 도로가 중복으로 존재할 수 있다.
  • 아무 도로도 연결되지 않은 동네가 존재 할 수 있다.

(M+2)번째 줄에는 두 개의 정수 |P|, |Q|가 주어진다.

  • |P|는 데리러 가기 좋은 동네의 수를 나타내는 1이상 N이하의 자연수다
  • |Q|는 바래다 주기 좋은 동네의 수를 나타내는 1이상 N이하의 자연수다

(M+3)번째 줄에는 P 그룹에 해당하는 동네의 번호가 공백으로 구분되어 주어진다.

(M+4)번째 줄에는 Q 그룹에 해당하는 동네의 번호가 공백으로 구분되어 주어진다.

  • 동네의 번호는 1번부터 N번으로 구분된다.
  • 한 그룹에 중복된 동네 번호가 주어지지 않는다.
  • P그룹과 Q그룹 사이에는 교집합이 존재할 수 있다.

출력

[1, K]의 시간동안 발생할 수 있는 드라이브 경로의 수는 몇 가지인지 출력하시오.

  • 경우의 수가 너무 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

6 6 2
4 1
5 1
2 1
2 5
5 6
3 6
2 3
1 2
6 5 2

예제 출력 1

10

  1. (1) - (2)
  2. (1) - (5)
  3. (2) - (5)
  4. (1) - (2) - (5)
  5. (1) - (5) - (2)
  6. (1) - (5) - (6)
  7. (2) - (1) - (2)
  8. (2) - (1) - (5)
  9. (2) - (5) - (2)
  10. (2) - (5) - (6)

예제 입력 2

6 3 2
1 4
5 2
3 6
3 3
1 2 3
6 5 4

예제 출력 2

3

  1. (1) - (4)
  2. (2) - (5)
  3. (3) - (6)

예제 입력 3

6 3 100
1 4
2 5
3 6
3 2
1 4 2
3 6

예제 출력 3

0

출처

University > 경인지역 6개대학 연합 > shake! 2020 E번