Let's call beauty of an array $b_1, b_2, \ldots, b_n$ ($n > 1$)  — $\min\limits_{1 \leq i < j \leq n} |b_i - b_j|$.

You're given an array $a_1, a_2, \ldots a_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-----

The first line contains integers $n, k$ ($2 \le k \le n \le 1000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^5$).


-----Output-----

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$.


-----Examples-----
Input
4 3
1 7 3 5

Output
8
Input
5 5
1 10 100 1000 10000

Output
9


-----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$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming


Solutions:
from collections import defaultdict
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
(n, m) = list(map(int, input().split()))
A = [0] + sorted(list(map(int, input().split())))
ans = 0
f = [[0] * (n + 10) for _ in range(m + 10)]
for x in range(1, (A[n] - A[1]) // (m - 1) + 1):
	for i in range(1, n + 1):
		f[1][i] = 1
	for i in range(2, m + 1):
		sum = 0
		pre = 1
		for j in range(1, n + 1):
			while pre <= n and A[pre] + x <= A[j]:
				sum += f[i - 1][pre]
				sum %= mod
				pre += 1
			f[i][j] = sum
	for i in range(1, n + 1):
		ans += f[m][i]
		ans %= mod
print(ans)