Hi all!

Following is the problem:

Dr Emmett Brown has decided to change his job and is now working as a Computer Science teacher in a high school. The Dr Brown's class has n students. Dr Brown wants to run a programming contest for his students. But his classroom only has k computers, so he needs to run a team contest. Dr thinks that the teamwork would be good for the students if the students in the team all have close levels of their skills. For each student Emmett Brown knows its skill level ai. He has decided to create teams in such way that for any two teams there is a number x such that students in one team have skill level at most x, and in the other team all students have skill level at least x. There must be exactly k teams, each team must have at least one student, but there is no upper limit for the number of students in one team. Help Doctor to find out how many ways are there for him to create the teams. Two ways are different if there are two students that are in the same team in of the them, and in different teams in the other. You should output the number of ways modulo 10^9 + 7.

Constraints: 1<=n, k<=2000 1<=ai<=n

Sample: n=3, k=2, a=[1,2,3] ans = 2

n=7, k=3, a=[2,4,3,4,3,3,2] ans = 53

Here is the editorial for the problem: http://mirror.codeforces.com/blog/entry/44517

Can someone please explain the editorial? I do not understand how the dp relation works and the intuition behind it.

Help is appreciated. Thanks!