BlitzCode, ediția 1 · Clasa a X-aCombinatoricăProbleme diverse de combinatorică
Problema Evolutie
Treaba a devenit cu adevărat serioasă pentru Matei după ce a primit rezultatele de la simularea bacalaureatului la biologie. Prea s-a distrat până acum, dar de astăzi trebuie serios să se apuce de treabă și să repete toată materia.
Părinții lui vor ca el să fie medicinist, însă adevărata lui dragoste este informatica — oricum e prea târziu și nu poate să își modifice materia la alegere pentru bac. În schimb, în timpul lucrului dedicat biologiei, Matei strecoară câte o problemă mai nesimțită de informatică.
Citind despre un anumit tip de celule în cartea portocalie de biologie, Matei se gândește la duratele de viață ale celulelor și despre cum evoluează acestea în timp. Mai precis, dacă avem n celule, fiecare celulă i are o durată de viață de ai secunde (1 ≤ i ≤ n). Celula cea mai fragilă/celulele cele mai fragile sunt cele care au cea mai mică durată de viață dintre cele n.
Cerință
Acum, problema lui Matei. În câte moduri putem alege duratele de viață ale celor n celule, știind că există cel puțin două celule fragile, iar toate celulele au durata de viață număr natural nenul mai mic sau egal cu o valoare m?
Date de intrare
Fișierul de intrare evolutie.in conține pe prima linie numerele naturale n și m separate printr-un spațiu.
Date de ieșire
Fișierul de ieșire evolutie.out conține un singur număr natural, reprezentând numărul de moduri de a alege duratele de viață ale celor n celule, respectând condițiile precizate. Deoarece această valoare este foarte mare, se cere aflarea răspunsului modulo 1.000.000.007.
Restricții și precizări
Subtask 1 (20 de puncte)
2 ≤ n ≤ 51 ≤ m ≤ 5
Subtask 2 (80 de puncte)
1.000.000 ≤ n ≤ 100.000.000100.000 ≤ m ≤ 500.000- Subtaskul acesta este mai nesimțit decât atitudinea lui Matei pentru biologie
Exemple
2 5
5
123456 123456
975101586
Explicația exemplelor
Pentru primul exemplu. Există 5 moduri de a alege viețile: fie au ambele durata 1, fie 2, …, fie 5.
Pentru al doilea exemplu. Există 975101586 de moduri de alege duratele de viață.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;