Najkraći

Zadana je prometna mreža neke države koju čine N gradova i M jednosmjernih cesta. Gradovi su označeni brojevima od 1 do N. Za svaku cestu poznati su polazni i odredišni grad, te njena duljina. Za cestu F kažemo da nastavlja cestu E ako je odredišni grad ceste E jednak polaznom gradu ceste F. Put od grada A do grada B je takav niz cesta u kojem svaka cesta nastavlja prethodnu cestu u nizu, polazni grad prve ceste je A, a odredišni grad zadnje ceste u nizu je B. Ukupna duljina puta je zbroj duljina svih cesta na putu. Za neki put od grada A do grada B kažemo da je najkraći ako ne postoji neki drugi put od grada A i grada B s manjom ukupnom duljinom. Vaš je zadatak da za svaku cestu pronañete koliko ima različitih najkraćih puteva koji sadrže tu cestu. Kako taj broj može biti velik ispišite ostatak pri djeljenju tog broja s brojem 1 000 000 007.