# Main

```
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef short i16;
typedef unsigned short u16;
typedef int i32;
typedef unsigned int u32;
typedef long int i64;
typedef unsigned long int u64;
typedef float f32;
typedef double f64;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	return 0;
}
```

I use Rust data type style because it's more logical and shorter.

# Math

## gcd

```
int gcd(int a, int b){
    int temp;
    while (b > 0){
        temp = a%b;
        a = b;
        b = temp;
    }
    return a;
}
```

## bigint
```
struct bigint{
    static const int LEN = 60;
    static const int BIGMOD = 10000;
    int s; // sign of big integer
    int vl, v[LEN];	// vl is length of v array
    bigint() : s(1) { vl = 0; } // eg. bigint x;
    bigint(long long a) { // eg. bigint x(a);
    s = 1; vl = 0;
        if (a < 0) {
            s = -1; a = -a;
        }
        while (a) {
            push_back(a % BIGMOD);
            a /= BIGMOD;
        }
    }
    bigint(string str) { // eg. bigint x(str);
    s = 1; vl = 0;
    int stPos = 0, num = 0;
    if (!str.empty() && str[0] == '-') {
        stPos = 1;
        s = -1;
    }
    for (int i=str.length()-1, q=1; i>=stPos; i--) {
        num += (str[i] - '0') * q;
        if ((q *= 10) >= BIGMOD) {
            push_back(num);
            num = 0; q = 1;
        }
    }
    if (num) push_back(num);
    }
    int len() const {
    return vl;
    }

    bool empty() const { return len() == 0; }

    void push_back(int x) {
    v[vl++] = x;
    }

    void pop_back() {
    vl--;
    }

    int back() const {
    return v[vl-1];
    }

    void n() {
    while (!empty() && !back()) pop_back();
    }

    void resize(int nl) {
    vl = nl;
    memset(v,0,sizeof(int)*vl);
    }
    void print() const {
    if (empty()) { putchar('0'); return; }
    if (s == -1) putchar('-');
    printf("%d", back());
    for (int i=len()-2; i>=0; i--) printf("%.4d",v[i]);
    }

    friend std::ostream& operator << (std::ostream& out, const bigint &a) {
    if (a.empty()) { out << "0"; return out; }
    if (a.s == -1) out << "-";
    out << a.back();
    for (int i=a.len()-2; i>=0; i--) {
      char str[10];
      snprintf(str, 5, "%.4d", a.v[i]);
      out << str;
    }
    return out;
    }
    int compare(const bigint &b)const {
    if (s != b.s) return s - b.s;
    if (s == -1) return -(-*this).compare(-b);
    if (len() != b.len()) return len()-b.len();//int
    for (int i=len()-1; i>=0; i--)
      if (v[i]!=b.v[i]) return v[i]-b.v[i];
    return 0;
    }
    bool operator < (const bigint &b)const{ return compare(b)<0; }
    bool operator <= (const bigint &b)const{ return compare(b)<=0; }
    bool operator == (const bigint &b)const{ return compare(b)==0; }
    bool operator != (const bigint &b)const{ return compare(b)!=0; }
    bool operator > (const bigint &b)const{ return compare(b)>0; }
    bool operator >= (const bigint &b)const{ return compare(b)>=0; }
    bigint operator - () const {
    bigint r = (*this);
    r.s = -r.s;
    return r;
    }
    bigint operator + (const bigint &b) const {
    if (s == -1) return -(-(*this)+(-b));
    if (b.s == -1) return (*this)-(-b);
    bigint r;
    int nl = max(len(), b.len());
    r.resize(nl + 1);
    for (int i=0; i<nl; i++) {
      if (i < len()) r.v[i] += v[i];
      if (i < b.len()) r.v[i] += b.v[i];
      if(r.v[i] >= BIGMOD) {
        r.v[i+1] += r.v[i] / BIGMOD;
        r.v[i] %= BIGMOD;
      }
    }
    r.n();
    return r;
    }
    bigint operator - (const bigint &b) const {
    if (s == -1) return -(-(*this)-(-b));
    if (b.s == -1) return (*this)+(-b);
    if ((*this) < b) return -(b-(*this));
    bigint r;
    r.resize(len());
    for (int i=0; i<len(); i++) {
      r.v[i] += v[i];
      if (i < b.len()) r.v[i] -= b.v[i];
      if (r.v[i] < 0) {
        r.v[i] += BIGMOD;
        r.v[i+1]--;
      }
    }
    r.n();
    return r;
    }
    bigint operator * (const bigint &b) {
    bigint r;
    r.resize(len() + b.len() + 1);
    r.s = s * b.s;
    for (int i=0; i<len(); i++) {
      for (int j=0; j<b.len(); j++) {
        r.v[i+j] += v[i] * b.v[j];
        if(r.v[i+j] >= BIGMOD) {
          r.v[i+j+1] += r.v[i+j] / BIGMOD;
          r.v[i+j] %= BIGMOD;
        }
      }
    }
    r.n();
    return r;
    }
    bigint operator / (const bigint &b) {
    bigint r;
    r.resize(max(1, len()-b.len()+1));
    int oriS = s;
    bigint b2 = b; // b2 = abs(b)
    s = b2.s = r.s = 1;
    for (int i=r.len()-1; i>=0; i--) {
      int d=0, u=BIGMOD-1;
      while(d<u) {
        int m = (d+u+1)>>1;
        r.v[i] = m;
        if((r*b2) > (*this)) u = m-1;
        else d = m;
      }
      r.v[i] = d;
    }
    s = oriS;
    r.s = s * b.s;
    r.n();
    return r;
    }
    bigint operator % (const bigint &b) {
    return (*this)-(*this)/b*b;
    }
};

```