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];
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.