Added some number theory stuff

1 files changed, 13 insertions, 0 deletions

diff --git a/Math/numtheory.cpp b/Math/numtheory.cpp
new file mode 100644
index 0000000..a950f57
--- /dev/null
+++ b/Math/numtheory.cpp
@@ -0,0 +1,13 @@
+constexpr ll MOD = 1e9+7;
+
+int pow(int base, int exp) {
+	int res = 1;
+	while (exp) {
+		if (exp & 1) res = ((ll)base * res) % MOD;
+		exp >>= 1;
+		base = ((ll)base * base) % MOD;
+	}
+	return res;
+}
+
+int inv(int x) { return pow(x, MOD - 2); }