We can solve the question using the recurrence dp[i][j]=dp[i-1][j-1]+dp[i-2][j-1]+.....+dp[1][j-1] where i is the index and j is the length of the sequence and using **K** BITs to speed up the calculation of the sum.

Is there any way to solve it using segment tree as a different approach?