Used DP + BIT, AC in 0.078
O(n*k*logn) solution.
Don't forget, % 10^9 every step.