Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Symbol Newtona $N \choose K$ (czytaj: N po K) oznacza liczbę kombinacji K-elementowych zbioru N-elementowego. Można go obliczyć na przykład ze wzoru: $${N \choose K} = \frac{N!}{K! \cdot (N - K)!}$$ gdzie symbol wykrzyknika oznacza silnię liczby czyli iloczyn kolejnych dodatnich liczb naturalnych do tej liczby. Na przykład: 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120.
W tym zadaniu sprawdzimy po prostu czy potrafisz liczyć symbol Newtona. Dla bardzo dużych wartości N oraz K. Powodzenia. Dla ułatwienia, wystarczy że podasz resztę z dzielenia wyniku przez 109 + 7.
Napisz program, który wczyta wartości N oraz K, wyznaczy wartość ${N \choose K} \bmod (10^9 + 7)$ i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne N oraz K oddzielone pojedynczym odstępem.
Wyjście
Twój program powinien wypisać na wyjście dokładnie jedną nieujemną liczbę całkowitą – resztę z dzielenia przez 109 + 7 z wartości symbolu Newtona N po K.
Ograniczenia
1 ≤ K ≤ N ≤ 109.
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
${6 \choose 3} = \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6}{1 \cdot 2 \cdot 3 \cdot 1 \cdot 2 \cdot 3} = 20$ |
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|