The problem is simply as the title says, 1<=N<=200 and 1<=M<=N. The number of permutations is required mod 1e9+7. I thought of multiple methods but I am stuck in each one of them:

1) For each position i, calculate ans[i], where ans[i] is the number of permutations which have at leasing one increasing sub-array of length M starting at i and don't have any increasing sub-arrays of length M starting at positions earlier than i. The final answer is sum of all ans[i]. But I can't calculate ans[i] properly (stuck at the part of ensuring that ans[i] doesn't include any increasing sub-arrays of length M starting at positions earlier than i).

2) calculate ans[x] for 1<=x<=M or M<=x<=N (as ans[1] = N! and ans[N] = 1). But I can't find a way to calculate ans[x] from ans[x+1] or from ans[x-1].

3) Find the answer using dynamic programming with state dp[i][j][k][l], where i is the current position, j is last number put, k is the length of longest increasing suffix, l is boolean representing whether an increasing sub-array of length M has been constructed or not. But I can't ensure that the new number I will try to put at position is is not put before at an earlier position.

I have a solution which might be enough; anyway, I think it can be optimized with prefix sums or something like that for better complexity.

dp[i][j][k] - state of a permutation where thei-th first numbers are already chosen,jnumbers smaller than thei-th one are free to be used and there is a increasing subarray ending at elementiwith lengthk.If

k=m, then you might just returnfactorial(n-i), i.e. just choose then-ilast elements in any way. Otherwise, you have two options for the (i+ 1)-th element: either it is greater than thei-th element or it is smaller. Note that the quantitygof numbers greater than thei-th one which are free to be used is simply (n-i) -j. Now, you can make the transitions inO(N):By doing partial sums on diagonals (for

g) and rows (for first part of the sum) you can do the transitions in achieving .@fofao_funk Thanks a lot for your easy-to-understand answer

@radoslav11 Thank you for the optimization