If you need a structure for modular numbers, here is my:↵
↵
↵
~~~~~↵
const int MOD = 1e9 + 7; //Or your one↵
↵
struct Number {↵
int value;↵
Number (int value) {↵
this->value = (MOD + value) % MOD;↵
}↵
↵
friend bool operator< (const Number& a, const Number& b) {↵
return a.value < b.value;↵
}↵
↵
friend bool operator== (const Number& a, const Number& b) {↵
return a.value == b.value;↵
}↵
↵
friend Number operator+ (const Number& a, const Number& b) {↵
return Number ((a.value + b.value) % MOD);↵
}↵
↵
friend Number operator- (const Number& a, const Number& b) {↵
return Number ((a.value - b.value + MOD) % MOD);↵
}↵
↵
friend Number operator* (const Number& a, const Number& b) {↵
return Number (int(1LL * a.value * b.value % MOD));↵
}↵
↵
friend Number operator^ (const Number& a, const Number& k) {↵
if (k == 0) return 1;↵
if (k == 1) return a;↵
Number res = a ^ Number (k.value/2);↵
return res * res * Number(k.value%2);↵
}↵
↵
↵
Number (int a, int k) {↵
if (k == 0) this->value = 1;↵
else if (k == 1) this->value = a;↵
else {↵
Number res = Number (a, k/2);↵
res = res * res * Number(a, k%2);↵
this->value = res.value;↵
}↵
}↵
↵
friend Number operator/ (const Number& a, const Number& b) {↵
return a * Number(b.value, MOD - 2);↵
}↵
↵
friend ostream& operator<<(ostream& os, const Number& a) {↵
os << a.value;↵
return os;↵
}↵
};↵
~~~~~↵
↵
↵
↵
~~~~~↵
const int MOD = 1e9 + 7;
↵
struct Number {↵
int value;↵
Number (int value) {↵
this->value = (MOD + value) % MOD;↵
}↵
↵
friend bool operator< (const Number& a, const Number& b) {↵
return a.value < b.value;↵
}↵
↵
friend bool operator== (const Number& a, const Number& b) {↵
return a.value == b.value;↵
}↵
↵
friend Number operator+ (const Number& a, const Number& b) {↵
return Number ((a.value + b.value) % MOD);↵
}↵
↵
friend Number operator- (const Number& a, const Number& b) {↵
return Number ((a.value - b.value + MOD) % MOD);↵
}↵
↵
friend Number operator* (const Number& a, const Number& b) {↵
return Number (int(1LL * a.value * b.value % MOD));↵
}↵
↵
friend Number operator^ (const Number& a, const Number& k) {↵
if (k == 0) return 1;↵
if (k == 1) return a;↵
Number res = a ^ Number (k.value/2);↵
return res * res * Number(k.value%2);↵
}↵
↵
↵
Number (int a, int k) {↵
if (k == 0) this->value = 1;↵
else if (k == 1) this->value = a;↵
else {↵
Number res = Number (a, k/2);↵
res = res * res * Number(a, k%2);↵
this->value = res.value;↵
}↵
}↵
↵
friend Number operator/ (const Number& a, const Number& b) {↵
return a * Number(b.value, MOD - 2);↵
}↵
↵
friend ostream& operator<<(ostream& os, const Number& a) {↵
os << a.value;↵
return os;↵
}↵
};↵
~~~~~↵
↵
