fork download
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const long long M = 1000000007;
  6. const long long STEP = 10000000;
  7.  
  8. // Tu wklejasz tablicę wygenerowaną przez poprzedni program
  9. // Zawiera ona wyniki dla: 0!, 10000000!, 20000000!, ..., 1000000000! mod (10^9 + 7)
  10. long long kamienie[] = {
  11. 1, /* TUTAJ WKLEJ WYGENEROWANE LICZBY, BĘDZIE ICH OKOŁO 100 */
  12. };
  13.  
  14. int main() {
  15. // Ekstremalne przyspieszenie strumieni (bardzo ważne przy rygorystycznych limitach czasu)
  16. ios_base::sync_with_stdio(false);
  17. cin.tie(NULL);
  18.  
  19. long long n;
  20. if (!(cin >> n)) return 0;
  21.  
  22. // Jeżeli N jest większe lub równe wartości modułu, jednym z czynników
  23. // silni będzie M, więc cała reszta z dzielenia zawsze da 0.
  24. if (n >= M) {
  25. cout << 0 << "\n";
  26. return 0;
  27. }
  28.  
  29. // Szukamy, od jakiego kamienia milowego możemy zacząć
  30. long long paczka = n / STEP;
  31. long long res = kamienie[paczka];
  32.  
  33. // Obliczamy od kąd musimy ręcznie domnażać (np. od 30 000 001)
  34. long long start = paczka * STEP + 1;
  35.  
  36. // Domnażamy resztę. Pętla wykona się maksymalnie 10 milionów razy (błyskawicznie)
  37. for (long long i = start; i <= n; ++i) {
  38. res = (res * i) % M;
  39. }
  40.  
  41. cout << res << "\n";
  42. return 0;
  43. }
Success #stdin #stdout 0s 5320KB
stdin
500000000
stdout
0