fix binomial0 & add test

3 files changed, 26 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 7c0916a..e3f59e6 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,8 @@ TESTS = \
 	datastructures/test/monotonicConvexHull.test \
 	datastructures/test/persistent.test \
 	graph/test/binary_lifting.test \
-	graph/test/LCA_sparse.test
+	graph/test/LCA_sparse.test \
+	math/test/binomial0.test
 
 LATEXMK = latexmk -interaction=nonstopmode
 
@@ -50,6 +51,8 @@ graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \
 	graph/binary_lifting.cpp graph/test/util.cpp
 graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \
 	graph/LCA_sparse.cpp datastructures/sparseTable.cpp graph/test/util.cpp
+math/test/binomial0.test: math/test/binomial0.cpp math/binomial0.cpp \
+	math/shortModInv.cpp
 
 FORCE:
 .PHONY: all pdf test clean cleanpdf cleantest FORCE
diff --git a/math/binomial0.cpp b/math/binomial0.cpp
index d9af917..f37aea5 100644
--- a/math/binomial0.cpp
+++ b/math/binomial0.cpp
@@ -10,5 +10,5 @@ void precalc() {
 
 ll calc_binom(ll n, ll k) {
 	if (n < 0 || n < k || k < 0) return 0;
-	return (fac[n] * fac[n-k] % mod) * fac[k] % mod;
+	return (fac[n] * inv[n-k] % mod) * inv[k] % mod;
 }
diff --git a/math/test/binomial0.cpp b/math/test/binomial0.cpp
new file mode 100644
index 0000000..d6c3a03
--- /dev/null
+++ b/math/test/binomial0.cpp
@@ -0,0 +1,21 @@
+constexpr ll mod = 1'000'000'007;
+
+#include "../shortModInv.cpp"
+#include "../binomial0.cpp"
+
+int main() {
+	precalc();
+	assert(calc_binom(5, -1) == 0);
+	assert(calc_binom(5, 0) == 1);
+	assert(calc_binom(5, 1) == 5);
+	assert(calc_binom(5, 2) == 10);
+	assert(calc_binom(5, 3) == 10);
+	assert(calc_binom(5, 4) == 5);
+	assert(calc_binom(5, 5) == 1);
+	assert(calc_binom(5, 6) == 0);
+	assert(calc_binom(0, 0) == 1);
+	assert(calc_binom(-1, 0) == 0);
+	assert(calc_binom(-1, -1) == 0);
+	assert(calc_binom(-1, -2) == 0);
+	assert(calc_binom(100'000, 50'000) == 149033233);
+}