Fişierul intrare/ieşire:cabana.in, cabana.outSursăONIS 2014, Runda 1
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.35 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cabana

În pădurea cu alune, aveau o cabană N pitici. În cabană sunt exact K camere în care se poate dormi. Cum somnul nu este deloc de neglijat în lumea piticilor, aceştia se joacă înainte de culcare astfel: Piticii intră pe rând în cabană, începând cu piticul 1, până la piticul N şi se duc în camera în care vor dormi. Un pitic îşi alege camera în care va dormi în felul următor:

  • Se duce în camera care a fost aleasă de cât mai puţini pitici.
  • Dacă sunt mai multe camere cu această proprietate, piticul va alege oricare dintre acestea.

Când ajunge Albă ca Zăpada în cabană, aceasta se întreabă:

  • Oare în câte moduri poate fi ocupată cabana de către cei N pitici?

Două moduri de ocupare a cabanei sunt considerate distincte dacă cel puţin o cameră conţine alţi pitici. Pentru ca Albă ca Zăpada este o prinţesă de treabă, aceasta vă cere răspunsul modulo 1000000007.

Date de intrare

Fişierul de intrare cabana.in conţine pe prima linie un număr natural T, reprezentând numărul de teste. Pe urmatoarele T linii, se vor găsi două numere N şi K, având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire cabana.out se vor găsi T linii, pe fiecare linie i găsindu-se răspunsul la întrebarea i.

Restricţii

  • T = 100.000
  • 1 ≤ N ≤ 1018
  • 1 ≤ K ≤ 1.000.000
  • Se garantează că toţi piticii încap în cabană.

Exemplu

cabana.incabana.out
2
3 2
5 2
4
8

Explicaţie

Pentru primul test, sunt 3 pitici şi 2 camere. Cele patru posibilităţi sunt:
1. Camera 1 este ocupată de piticii 1 şi 3, iar camera 2 de piticul 2.
2. Camera 1 este ocupata de piticul 1, iar camera 2 de piticii 2 şi 3.
3. Camera 1 este ocupata de piticul 2 şi 3, iar camera 2 de piticul 1.
4. Camera 1 este ocupata de piticul 2, iar camera 2 de piticii 1 şi 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content