시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB21150.000%

## 문제

Today is the long-awaited day for all school students – the first holiday for the new school year. Our main heroine Deni is now in grade 10. She prepared for today – she found that there are N stores downtown and she plans to visit some of them with her friends. But Deni and her friends don’t like some of the connections between the stores and they won’t use them. So they have made a list of M pairs of stores such that a pair (x, y) is from the list if they like the connection from store x to y and of course they can reach store x from y and for every pair they have determined the time for travelling the connection (it is the same in both directions). There are no pairs with stores with the same numbers and there are no duplicate pairs.

Deni is very superstitious and one of the superstitions in which she believes is that the total time for travelling must be divisible by D. Deni and her friends don’t have unlimited time so the maximum time they can spend travelling is K. As all girls, Deni is very curious and she starts to count the number of different routes for visiting some of the stores (a store can be visitted more than once). Unfortunately, this number can be large so Deni remembers that she knows you – very good programmer and asks you to write the program superstition, which counts the number of valid routes. One route is valid if it uses the connections from the list of pairs, the total time for travelling is divisible by D and it is ≤ K. Two routes are different if there is a difference in the sequences of visited stores. You immediately notice that the answer can be very large and thus Deni tells you that she only wants the remainder when the answer is divided by 1,000,000,007.

## 입력

From the first line of the standard input read four integers N, M, D and K. From each of the next М lines read three integers xi, yi and ti – bidirectional connection between xi and yi with time of travel ti (1 ≤ i ≤ M).

## 출력

The number of different valid routes. Since this number may be quite large, you are required to print its remainder when divided by 1,000,000,007.

## 제한

• 2 ≤ N ≤ 80
• 2 ≤ M ≤ 3160
• 2 ≤ D ≤ K ≤ 109
• 1 ≤ ti ≤ 10

## 서브태스크 1 (5점)

• N ≤ 5, M ≤ 10, D ≤ 12, K ≤ 12

## 서브태스크 2 (30점)

• N ≤ 80, M ≤ 3160, D ≤ 104, K ≤ 104

## 서브태스크 3 (10점)

• N ≤ 20, M ≤ 190, D ≤ 109, K ≤ 109
• D = K
• Σti ≤ 200

## 서브태스크 4 (20점)

• N ≤ 20, M ≤ 190, D ≤ 109, K ≤ 109
• Σti ≤ 200

## 서브태스크 5 (15점)

• N ≤ 30, M ≤ 435 D ≤ 109, K ≤ 109
• D = K

## 서브태스크 6 (20점)

• N ≤ 30, M ≤ 435, D ≤ 109, K ≤ 109

## 예제 입력 1

3 3 2 2
1 2 1
2 3 2
3 1 1


## 예제 출력 1

8


Here D = K = 2 i.e. the needed routes are only with total time 2. They are:

1 – 2 – 1      2 – 1 – 2      3 – 1 – 3
1 – 3 – 1        2 – 3            3 – 2
2 – 1 – 3                     3 – 1 – 2

Notice that stores and connections can be repeated more than once.

## 예제 입력 2

5 7 5 10
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4


## 예제 출력 2

58


Because D < K the needed routes are with total time 5 and 10.

## 예제 입력 3

5 9 2 20
1 2 1
2 3 2
3 1 1
3 4 1
4 5 2
5 3 1
1 5 1
2 4 1
2 5 1


## 예제 출력 3

989802661


Here the real answer is a big number so the output is only its remainder when divided by 1,000,000,007.

## 예제 입력 4

5 7 5000000 5000000
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4


## 예제 출력 4

598634781


Here the real answer is a big number so the output is only its remainder when divided by 1,000,000,007.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.