Hi,Codeforces! I need your help!

There is a kind of integer sequence of length (n+k). (k<=n)

Constraints follow:

1. For every element in sequence, its value is either -1 or a positive integer.

2. The number of -1's occurrences is n and the number of positive integers's occurrences is k.

3. The sum of all positive integers equals n.

4. Any prefix sum of the sequence is non-negative.

Now you must calculate the number of different sequences satisfying the constraints above.

Is there a general formula for this answer? Most thanks.

I have met a problem about LCS so hard for me. There are two strings S1,S2. |S1|,|S2|<=5000. Let n is the max length of two strings. Is there a O(n^2)solution which can find S2's all subtrings's longest common sequence with S1 ? Most thanks!