高精

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct BigInt
{
    vector<int> vec;
    inline BigInt operator+(BigInt t)
    {
        int sz = max(vec.size(), t.vec.size());
        vector<int> res(sz);
        int cry = 0;
        for (int i = 0; i < sz; i++)
        {
            if (vec.size() > i)
                res[i] += vec[i];
            if (t.vec.size() > i)
                res[i] += t.vec[i];
            res[i] += cry;
            cry = res[i] > 9;
            res[i] %= 10;
        }
        if (cry)
            res.emplace_back(1);
        return (BigInt){res};
    }
    inline BigInt operator-(BigInt t)
    {
        vector<int> res = vec;
        int cry = 0;
        for (int i = 0; i < vec.size(); i++)
        {
            if (t.vec.size() > i)
                res[i] -= t.vec[i];
            res[i] -= cry;
            cry = 0;
            if (res[i] < 0)
            {
                res[i] += 10;
                cry = 1;
            }
        }
        while (res.size() > 1 && !res.back())
            res.pop_back();
        return (BigInt){res};
    }
    inline BigInt operator*(BigInt t)
    {
        vector<int> res(vec.size() + t.vec.size() - 1);
        for (int i = 0; i < vec.size(); i++)
            for (int j = 0; j < t.vec.size(); j++)
                res[i + j] += vec[i] * t.vec[j];
        for (int i = 0; i < res.size() - 1; i++)
            res[i + 1] += res[i] / 10, res[i] %= 10;
        while (res.back() > 9)
        {
            res.emplace_back(res.back() / 10);
            res[res.size() - 2] %= 10;
        }
        return (BigInt){res};
    }
    inline BigInt operator/(int k)
    {
        vector<int> res;
        reverse(vec.begin(), vec.end());
        int cur = 0, beg = 0;
        for (int i = 0; i < vec.size(); i++)
        {
            cur = cur * 10 + vec[i];
            if (cur >= k)
            {
                res.emplace_back(cur / k);
                cur %= k;
                beg = 1;
            }
            else if (beg)
                res.emplace_back(0);
        }
        reverse(vec.begin(), vec.end());
        reverse(res.begin(), res.end());
        if (res.empty())
            res.emplace_back(0);
        return (BigInt){res};
    }
    inline BigInt toBigInt(int k)
    {
        vector<int> res;
        while (k)
        {
            res.emplace_back(k % 10);
            k /= 10;
        }
        return (BigInt){res};
    }
    inline BigInt operator+(int k)
    {
        return (*this) + toBigInt(k);
    }
    inline BigInt operator-(int k)
    {
        return (*this) - toBigInt(k);
    }
    inline BigInt operator*(int k)
    {
        return (*this) * toBigInt(k);
    }
    inline bool operator<=(BigInt t)
    {
        if (vec.size() != t.vec.size())
            return vec.size() < t.vec.size();
        for (int i = vec.size() - 1; ~i; i--)
            if (vec[i] != t.vec[i])
                return vec[i] < t.vec[i];
        return true;
    }
    inline BigInt sqrt()
    {
        BigInt l = toBigInt(0), r = toBigInt(1), num = *this;
        while (r * r <= num)
            r = r * 2;
        while (l <= r)
        {
            BigInt mid = (l + r) / 2;
            if (mid * mid <= num)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l - 1;
    }
    inline void read()
    {
        string s;
        cin >> s;
        vec.resize(s.size());
        for (int i = 0; i < s.size(); i++)
            vec[s.size() - i - 1] = s[i] - '0';
    }
    inline void print()
    {
        for (int i = vec.size() - 1; ~i; i--)
            cout << vec[i];
    }
    inline int mod2()
    {
        return vec.back() & 1;
    }
    inline int mod3()
    {
        int res = 0;
        for (int x : vec)
            (res += x) %= 3;
        return res;
    }
    inline BigInt operator^(ll k)
    {
        BigInt res = toBigInt(1), base = *this;
        while (k)
        {
            if (k & 1)
                res = res * base;
            base = base * base;
            k >>= 1;
        }
        return res;
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}