Science Fair

All submissions for this problem are available.
This is a story of city Chef Land. The transport network of the city contains V intersections and E bidirectional roads. The intersections are numbered from 1 to V. Every intersection can be reached from every other intersection. The road E_{i} has length W_{i}. The Mayor is organizing a Science Festival at intersection F.
The N students studying in School of Chef Land have requested their principal to send them to the Festival. Each student lives at an intersection (student i lives at intersection P_{i}). The school is present at intersection S.
The principle wants to send randomly some of the N students to the Science Festival. He writes their names on an Official List and gives it to the bus driver to arrange the transport. The probability that name of i^{th} student is written on the list is equal to the percentage marks M_{i} he receives in Science.
The driver's job is to drive the school bus from school S to Festival F picking up all the students mentioned on the official list. Since all the students are super excited to visit the festival, therefore if the bus goes through the intersection they are living on, they will on board the bus even if their name was not written on the official list by the principal.
We know that the bus driver doesn’t like talkative people in the bus. Also, for every student i we know his talkativeness value T_{i}. The talkativeness of the trip done by driver from S to F is defined as the product of Talkativeness of all the students that got into the bus.
For a trip: The driver faces a cost(Trip) = Length(Trip) + (Talkativeness(Trip) modulo 10^{9}+7 ). Therefore the driver always chooses the path with minimum cost. He also charges this amount from the principal.
If the driver receives an empty list he cancels the trip and the cost is 0.
The principal wants to know the expected value of money paid by him to the driver for a single trip.
Input
 The first line contains 4 space separated integers V, E, S, F.
 The second line contains a single integer N.
 i^{th} line of the next N lines contains 3 integers each P_{i} T_{i }M_{i}.
 The next E lines contains 3 integers each u v w denoting a road of length w between intersections u and v.
Output
Print a single integer (A*B^{}^{1}) mod 10^{9}+7 where A/B is the expected money paid by the principal and gcd(A, B) = 1. B^{}^{1} is the modular inverse of B modulo 10^{9}+7
Constraints
 1 ≤ V ≤ 1000
 1 ≤ E ≤ 3000
 1 ≤ N ≤ 16
 1 ≤ S, F, P_{i} ≤ V
 S, F, P_{i}'s are all distinct
 0 ≤ M_{i} ≤ 100
 0 ≤ T_{i} ≤ 10^{9}+6
 1 ≤ w ≤ 10^{6}
 1 ≤ u, v ≤ V
 There is at most 1 road between any pair of intersection
 Every intersection can be reached from every other intersection.
 u ≠ v
Example
Input: 5 5 1 5 3 2 1 50 3 1 50 4 1 50 1 2 1 1 3 1 1 4 1 2 5 1 3 5 1 Output: 125000005
Explanation
Official List  Probability  Path travelled  Length  Students in trip 
Talk Value 
Cost 
{}  1/8  None  0  None  0  0 
{2}  1/8  125  2  {2}  1  3 
{3}  1/8  135  2  {3}  1  3 
{4}  1/8  14135  4  {3, 4}  1*1  5 
{2, 3}  1/8  12135  4  {2, 3}  1*1  5 
{2, 4}  1/8  14125  4  {2, 4}  1*1  5 
{3, 4}  1/8  14135  4  {3, 4}  1*1  5 
{2, 3, 4}  1/8  1412135  6  {2, 3, 4}  1*1*1  7 
Expected cost =(0+3+3+5+5+5+5+7)/8 = 33/8 = 33 * 8^{}^{1} mod 10^{9}+7= 33*125000001 mod 10^{9}+7 = 125000005
Author:  usaxena95 
Editorial  https://discuss.codechef.com/problems/SCIENCEF 
Tags  acm17kgp, bitmask, dynamicprogramming, hard, kgp17rol, tsp, usaxena95 
Date Added:  5122017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 