dp2 [ i ] to store the no of ways to get to a bad shift in i moves
long dp1 [ ] = new long [ k + 1 ] ; long dp2 [ ] = new long [ k + 1 ] ; if ( s == t ) { dp1 [ 0 ] = 1 ; dp2 [ 0 ] = 0 ; } else { dp1 [ 0 ] = 0 ; dp2 [ 0 ] = 1 ; }