Please help with weird behavior of Modulo.

I have DP solution as follow, for last statement in the loop I use

```
T[r][c] = (T[r][c] + MOD) % MOD;
```

all test can pass

but if I use

```
T[r][c] = T[r][c] % MOD;
```

There are weired negative result showing up. I can't understand why this happens, why do I have to add MOD(10^9 + 7) before doing modulo operation? the long integer should have no overflow.

```
public class Solution {
//equation: T[n,k] = Sum(i= k-n+1 ~ k){T[n-1, i]}
//T[n,k-1] = Sum(i=0~n-1){T[n-1,k-1-i]}
//recursion: T[n,k] = T[n,k-1] - d(k-n >=0)*T[n-1, k-n] + T[n-1, k]
//base case: T[*, 0]=1; T[0,*]=0; T[1,*]=0;
//0<=k<=n*(n-1)
static final long MOD = 1000000007L;
public int kInversePairs(int n, int k) {
long[][] T = new long[n+1][k+1];
for(int t=0; t<=n; t++){
T[t][0] = 1;
}
for(int r=2; r<=n; r++){
for(int c=1; c<=k ; c++){
T[r][c] = T[r-1][c]
- ((c >=r) ? T[r-1][c-r] : 0)
+ T[r][c-1];
T[r][c] = (T[r][c] + MOD) % MOD;
}
}
return (int) T[n][k];
}
}
```