Properties Of Modulo I am just starting with competitive programing and usually numbers get way too large so we tend to work with $$ \mod 10^9+7$$
I am familiar with some properties of modulo like,
$$(a+b) \mod c = (a\mod c+b\mod c) \mod c$$
$$(a-b) \mod c = (a\mod c-b\mod c) \mod c$$
$$(a*b) \mod c = (a\mod c*b\mod c) \mod c$$ 
But recently I stumbled upon this formula, 
$$y=\frac{4a^3-a^2}{3}$$
This is the Faulhaber Formula for $\sum_{i=0}^{n}{i^5}$, where $a=\sum_{i=0}^{n}{i}$.
Now this is what has me stuck.
In my scenario $a\approx10^{16}$ and the largest value I can store is $\approx 10^{19}$.
and I want to evaluate,
$$\frac{4a^3-a^2}{3} \mod 10^9+7$$
Clearly I cannot calculate $a^3$ due to overflow also I am finding it hard to distribute the modulo because of the $3$ in the denominator. How do I get around this?
Any suggestions will be helpful. Thanks.
 A: We can use 
$$a^3 \pmod{p} \equiv \color{red}[\color{blue}[(a \pmod{p}) \cdot (a \pmod{p})\pmod{p}\color{blue}] \cdot (a \pmod{p})  \color{red}]\pmod{p}$$
That is we keep computing modulo after each step of computation, hence the number stays within the limit of your computation.
A: You can take mod while multiplying numbers. After taking modulo separately to $a^3$ and $a^2$, you can still get the correct answer.
Below is a piece of C++ code that show how you can take mod of $a^2$, $a^3$, etc.
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int main(){
    long long a = /*something from the input*/;
    a %= mod;
    long long a2 = a;
    a2 *= a; a2 %= mod;
    //^ There we got the value of a^2 mod (1e9 + 7).
    long long a3 = a2;
    a3 *= a; a3 %= mod;
    //^ We got the value of a^3 mod (1e9 + 7) similarly.
    //TODO: implementation
}

You then substitute the values of $a^2$ and $a^3$ into your formula.
If you encounter greater powers later, just use the big mod algorithm:
long long big_mod(long long base, long long power, long long mod){
    if (power == 0) return 1;
    else if (power == 1) return base%mod;
    else{
        if (power%2 == 1) return (base * big_mod(base, power-1, mod))%mod;
        else return (big_mod(base, power/2, mod) * big_mod(base, power/2, mod))%mod;
    }
}

The algorithm above runs in $\mathcal{O}(\log(\operatorname{power}))$ time.
A: Hint $\bmod 10^{\large 9}\!+7\!:\,\ 10^{\large 9}\equiv -7\,\Rightarrow\ 10^{\large 10}\equiv -70,\,\ldots, 10^{\large 18}\equiv (-7)^{\large 2}\equiv 49,\,\ldots$
and $\ \bmod\, \color{#c00}2\!+\!3n\!:\,\  \dfrac{1}3\,\equiv\, \dfrac{1+ 2\!+\!3n} 3\,\equiv\, 1\!+\!n\ \ $ [here $\bmod 3\!:\ 10^{\large 9}\!+7\equiv 1^{\large 9}\!+1\equiv \color{#c00}2\:\!$]
