How to solve this problem?

find the number of permutations of length N that have longest increasing subsequence equal to K

1<=N<=40 , 1<=K<=5 problem link

Can anyone help me to solve this problem?

Given a sequence A (of length N) of positive integers and an integer k, find out how many of its sub-sequences are k-medial. where k-medial means that the median of this subsequence is k. A sub-sequence of A is any sequence {A[i], A[i+1], A[i+2] ... A[j]}, where 0 ≤ i ≤ j < N.

if you participated in national olympiads or IOI talk about your strategy