You are given an array A = [1, 2, 3, ..., n]:     

How many sequences ($S_{1}$) can you get after exact k adjacent swaps on A? 

How many sequences ($S_{2}$) can you get after at most k swaps on A?  

An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. 

A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j.

Input Format

First and only line contains n and k separated by space.    

Constraints

1 ≤ n ≤ 2500 

1 ≤ k ≤ 2500      

Output Format

Output $S_{1}$ % MOD and $S_{2} $% MOD in one line, where MOD = 1000000007.    

Sample Input
3 2

Sample Output
3 6

Explanation
Original array: [1, 2, 3]
1. After 2 adjacent swaps:
We can get [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S1 == 3

2. After at most 2 swaps:
1) After 0 swap: [1, 2, 3]
2) After 1 swap: [2, 1, 3], [3, 2, 1], [1, 3, 2].
3) After 2 swaps: [1, 2, 3], [2, 3, 1], [3, 1, 2]
==> S2 == 6

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from itertools import accumulate, chain, islice
from sys import stderr
MOD = 1000000007

def adjswap(n, k):
	if n == 1:
		return int(k == 0)
	permcount = [1] * (k + 1)
	for nperm in range(3, n + 1):
		oldpermcount = permcount
		cumsum = list(accumulate(oldpermcount))
		permcount = chain(islice(cumsum, nperm), (a - b for (a, b) in zip(islice(cumsum, nperm, None), cumsum)))
		permcount = [x % MOD for x in permcount]
	return permcount[-1]

def anyswap(n, k):
	arr = [1] * (k + 1)
	for i in range(n):
		arr = [(a + i * b) % MOD for (a, b) in zip(arr, [0] + arr[:-1])]
	return arr[-1]

def old():
	key = (n, k)
	if key in cache:
		return cache[key]
	if n <= 1 or k == 0:
		ans = 1
	else:
		ans = (anyswap(n - 1, k, cache) + (n - 1) * anyswap(n - 1, k - 1, cache)) % MOD
	cache[key] = ans
	return ans
(n, k) = [int(f) for f in input().split()]
print(adjswap(n, k), anyswap(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


mod = 10 ** 9 + 7

def helper1(n, k):
	dp1 = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		dp1[i][0] = 1
	for i in range(2, n + 1):
		for j in range(1, k + 1):
			dp1[i][j] = dp1[i][j - 1] + dp1[i - 1][j]
			if j - i >= 0:
				dp1[i][j] -= dp1[i - 1][j - i]
			dp1[i][j] %= mod
	return sum((dp1[n][kk] for kk in range(k, -1, -2))) % mod

def helper2(n, k):
	dp2 = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	dp2[1][1] = 1
	for i in range(1, n):
		for j in range(1, i + 1):
			dp2[i + 1][j + 1] = (dp2[i + 1][j + 1] + dp2[i][j]) % mod
			dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j] * i) % mod
	return sum((dp2[n][kk] for kk in range(max(n - k, 0), n + 1))) % mod

def swapPermutation(n, k):
	return '%d %d' % (helper1(n, k), helper2(n, k))
nk = input().split()
n = int(nk[0])
k = int(nk[1])
result = swapPermutation(n, k)
print(result)


(N, K) = map(int, input().split(' '))
(A, B, C, D, M) = ([None] * (K + 1), [3] * (K + 1), [0] * (N + 1), [0] * (N + 1), 10 ** 9 + 7)
(B[0], B[1], A[0], C[1]) = (1, 2, 1, 1)
for n in range(4, N + 1):
	for k in range(1, K + 1):
		A[k] = (B[k] + A[k - 1] - (0 if k < n else B[k - n])) % M
	(B, A) = (A, B)
for i in range(2, N + 1):
	for j in range(1, i + 1):
		D[j] = (C[j - 1] + (i - 1) * C[j]) % M
	(C, D) = (D, C)
print('%d %d' % (B[-1], sum(C[N - min(K, N - 1):N + 1]) % M))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import math
import os
import random
import re
import sys

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import math
import os
import random
import re
import sys
import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


from itertools import accumulate, chain, islice
from sys import stderr
MOD = 1000000007

def adjswap(n, k):
	if n == 1:
		return int(k == 0)
	permcount = [1] * (k + 1)
	for nperm in range(3, n + 1):
		oldpermcount = permcount
		cumsum = list(accumulate(oldpermcount))
		permcount = chain(islice(cumsum, nperm), (a - b for (a, b) in zip(islice(cumsum, nperm, None), cumsum)))
		permcount = [x % MOD for x in permcount]
	return permcount[-1]

def anyswap(n, k):
	arr = [1] * (k + 1)
	for i in range(n):
		arr = [(a + i * b) % MOD for (a, b) in zip(arr, [0] + arr[:-1])]
	return arr[-1]

def old():
	key = (n, k)
	if key in cache:
		return cache[key]
	if n <= 1 or k == 0:
		ans = 1
	else:
		ans = (anyswap(n - 1, k, cache) + (n - 1) * anyswap(n - 1, k - 1, cache)) % MOD
	cache[key] = ans
	return ans
(n, k) = [int(f) for f in input().split()]
print(adjswap(n, k), anyswap(n, k))


from itertools import accumulate, chain, islice
from sys import stderr
MOD = 1000000007

def adjswap(n, k):
	if n == 1:
		return int(k == 0)
	permcount = [1] * (k + 1)
	for nperm in range(3, n + 1):
		oldpermcount = permcount
		cumsum = list(accumulate(oldpermcount))
		permcount = chain(islice(cumsum, nperm), (a - b for (a, b) in zip(islice(cumsum, nperm, None), cumsum)))
		permcount = [x % MOD for x in permcount]
	return permcount[-1]

def anyswap(n, k):
	arr = [1] * (k + 1)
	for i in range(n):
		arr = [(a + i * b) % MOD for (a, b) in zip(arr, [0] + arr[:-1])]
	return arr[-1]

def old():
	key = (n, k)
	if key in cache:
		return cache[key]
	if n <= 1 or k == 0:
		ans = 1
	else:
		ans = (anyswap(n - 1, k, cache) + (n - 1) * anyswap(n - 1, k - 1, cache)) % MOD
	cache[key] = ans
	return ans
(n, k) = [int(f) for f in input().split()]
print(adjswap(n, k), anyswap(n, k))


from itertools import accumulate, chain, islice
from sys import stderr
MOD = 1000000007

def adjswap(n, k):
	if n == 1:
		return int(k == 0)
	permcount = [1] * (k + 1)
	for nperm in range(3, n + 1):
		oldpermcount = permcount
		cumsum = list(accumulate(oldpermcount))
		permcount = chain(islice(cumsum, nperm), (a - b for (a, b) in zip(islice(cumsum, nperm, None), cumsum)))
		permcount = [x % MOD for x in permcount]
	return permcount[-1]

def anyswap(n, k):
	arr = [1] * (k + 1)
	for i in range(n):
		arr = [(a + i * b) % MOD for (a, b) in zip(arr, [0] + arr[:-1])]
	return arr[-1]

def old():
	key = (n, k)
	if key in cache:
		return cache[key]
	if n <= 1 or k == 0:
		ans = 1
	else:
		ans = (anyswap(n - 1, k, cache) + (n - 1) * anyswap(n - 1, k - 1, cache)) % MOD
	cache[key] = ans
	return ans
(n, k) = [int(f) for f in input().split()]
print(adjswap(n, k), anyswap(n, k))


from itertools import accumulate, chain, islice
from sys import stderr
MOD = 1000000007

def adjswap(n, k):
	if n == 1:
		return int(k == 0)
	permcount = [1] * (k + 1)
	for nperm in range(3, n + 1):
		oldpermcount = permcount
		cumsum = list(accumulate(oldpermcount))
		permcount = chain(islice(cumsum, nperm), (a - b for (a, b) in zip(islice(cumsum, nperm, None), cumsum)))
		permcount = [x % MOD for x in permcount]
	return permcount[-1]

def anyswap(n, k):
	arr = [1] * (k + 1)
	for i in range(n):
		arr = [(a + i * b) % MOD for (a, b) in zip(arr, [0] + arr[:-1])]
	return arr[-1]

def old():
	key = (n, k)
	if key in cache:
		return cache[key]
	if n <= 1 or k == 0:
		ans = 1
	else:
		ans = (anyswap(n - 1, k, cache) + (n - 1) * anyswap(n - 1, k - 1, cache)) % MOD
	cache[key] = ans
	return ans
(n, k) = [int(f) for f in input().split()]
print(adjswap(n, k), anyswap(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import math
import os
import random
import re
import sys

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))


import sys
import math

def adjSwaps(n, k):
	if k == 0:
		return 1
	else:
		cntksteps = [1] * (k + 1)
		tmp = [0] * (k + 1)
		for i in range(3, n + 1):
			prefixSum = 0
			for j in range(min(i, k + 1)):
				prefixSum += cntksteps[j]
				prefixSum %= 1000000007
				tmp[j] = prefixSum
			for j in range(i, k + 1):
				prefixSum += cntksteps[j]
				prefixSum -= cntksteps[j - i]
				tmp[j] = prefixSum
			for j in range(k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007

def anySwaps(n, k):
	if k == 0:
		return 1
	elif n <= k:
		return math.factorial(n) % 1000000007
	else:
		tmp = [0] * (k + 1)
		cntksteps = [2] * (k + 1)
		cntksteps[0] = 1
		for i in range(3, n + 1):
			for j in range(1, k + 1):
				tmp[j] = (cntksteps[j] + (i - 1) * cntksteps[j - 1]) % 1000000007
			for j in range(1, k + 1):
				cntksteps[j] = tmp[j]
		return cntksteps[k] % 1000000007
f = sys.stdin
tmp = f.readline().split()
n = int(tmp[0])
k = int(tmp[1])
print(adjSwaps(n, k), anySwaps(n, k))