Diferențe pentru problema/superstition între reviziile #1 si #2

== include(page="template/taskheader" task_id="superstition") ==

Poveste și cerință...

Astăzi  este  cea  mai  așteptată  zi  pentru  toți  elevii, prima  vacanță  din  noul  an școlar. Eroina  noastră principală Deni este clasa a X-a. S-a pregătit pentru ziua de azi, a aflat că sunt $N$ magazine în oraș și a plănuit să viziteze unele dintre ele cu prietenii. Anumite străzi dintre magazine nu sunt preferate de Deni și prietenii ei și de aceea  nu  le  vor  folosi. Așadar, aceștia au  creat  o  listă  de $M$ perechi  de  magazine  de forma $(x, y)4, având semnificația că există o stradă (bidirecțională) acceptată de Deni ce leagă magazinul cu numărul $x$ de magazinul cu numărul [$y$]. În plus,  pentru  fiecare  pereche  din  listă  au  determinat  timpul  necesar  parcurgerii străzii corespunzătoare (care este acela și pentrutraversarea în ambele direcții). În listă nu există perechi între magazine cu același număr și nici perechi duplicate.
 
Deni este foarte superstițioasă și una dintre superstițiile în care ea crede este că timpul destinat întregii de plasări trebuie să fie divizibil cu [$D$]. Deni și prietenii ei nu au timp nelimitat așacă timpul maxim pe care ei îl pot petrece este [$K$]. Ca orice fată, Deni este foarte curioasă și începe să numere câte rute diferite pentru a vizita unele dintre magazine există (un magazin poate fi vizitat de mai multe ori). Din păcate acest număr poate fi foarte mare iar Deni își  aduce  aminte  că  te cunoaște  pe  tine, un  foarte  bun  programator și  îți  cere  să  scrii  programul care numără câte rute valide există. O rută este validă dacă folosește doar străzi din lista de perechi dată
și  timpul  total  de  traversare  este  divizibil  cu $D$ și este cel  mult [$K$]. Două  rute se consideră diferite dacă secvențele de magazine vizitate în ordine în cadrul acestora sunt diferite. Îți dai imediat seama că răspunsul poate fi foarte mare, de aceea Deni îțispune că vrea doar restul la împărțirea cu $1 000 000 007$ al numărului determinat.

h2. Date de intrare