← Home
write a go solution for Description:
Let's call beauty of an array b_1,b_2,ldots,b_n (n>1)  — minlimits_1<=i<j<=n|b_i-b_j|.

You're given an array a_1,a_2,ldotsa_n and a number k. Calculate the sum of beauty over all subsequences of the array of length exactly k. As this number can be very large, output it modulo 998244353.

A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

Input Format:
The first line contains integers n,k (2<=k<=n<=1000).

The second line contains n integers a_1,a_2,ldots,a_n (0<=a_i<=10^5).

Output Format:
Output one integer — the sum of beauty over all subsequences of the array of length exactly k. As this number can be very large, output it modulo 998244353.

Note:
In the first example, there are 4 subsequences of length 3 — [1,7,3], [1,3,5], [7,3,5], [1,7,5], each of which has beauty 2, so answer is 8.

In the second example, there is only one subsequence of length 5 — the whole array, which has the beauty equal to |10-1|=9.. Output only the code with no comments, explanation, or additional text.