Let's consider a random permutation p_{1}, p_{2}, ..., p_{N} of numbers 1, 2, ..., N and calculate the value F=(X_{2}+...+X_{N-1})^{K}, where X_{i} equals 1 if one of the following two conditions holds: p_{i-1} < p_{i} > p_{i+1} or p_{i-1} > p_{i} < p_{i+1} and X_{i} equals 0 otherwise. What is the expected value of F?

Input Format: 

The first line contains two integers K and N.

Output Format: 

Print the expected value of F as an irreducible fraction p / q. Follow sample input for more clarification.

Constraints: 

1000 <= N <= 10^{9} 

1 <= K <= 5

Sample input  

1 1000

Sample Output  

1996 / 3

Difficulty: MEDIUM_HARD
Tags: Probability

Starter code:

Solutions:
import sys
from fractions import gcd, Fraction
from itertools import permutations
DN = 11
DA = [2, 20, 90, 108, 240, 552, 328, 640, 420, 1428, 1652, 2660, 658, 1960, 1890, 3192, 504, 2268, 3892, 5656, 3038, 8204, 6426, 11592, 922, 3676, 5454, 8208, 3456, 9612, 7988, 14144, 420, 2352, 5348, 7280, 6202, 15820, 11130, 20748, 3698, 13880, 18570, 28752, 9480, 27348, 24352, 42220, 922, 4600, 9150, 12828, 9000, 23472, 17228, 31700, 4200, 16128, 22372, 34300, 12278, 35000, 30450, 53172, 240, 1608, 4552, 5920, 6998, 17180, 11310, 21492, 6202, 22420, 28290, 44508, 12960, 37992, 35048, 60080, 3038, 14540, 27150, 38652, 24000, 63648, 48112, 87760, 9000, 35352, 50888, 77240, 29962, 84460, 71850, 126348, 658, 3940, 9810, 13092, 12960, 32448, 22112, 41600, 9480, 34872, 45208, 70600, 21782, 63380, 57510, 99108, 3456, 16872, 32408, 45824, 29962, 78916, 58914, 107868, 12278, 47804, 67806, 103332, 38784, 109848, 94312, 165376, 90, 702, 2378, 2990, 4552, 10870, 6840, 13158, 5348, 18830, 22860, 36342, 9810, 28998, 27322, 46510, 3892, 18130, 32580, 46818, 27150, 72642, 55838, 101330, 9150, 36258, 53062, 80170, 32408, 90770, 76320, 134682, 1652, 9590, 22860, 30798, 28290, 71502, 49498, 92710, 18570, 69078, 91082, 141590, 45208, 130990, 117720, 203502, 5454, 27018, 53062, 74626, 50888, 133274, 98496, 180882, 22372, 86506, 121284, 185418, 67806, 192762, 166718, 291674, 328, 2290, 6840, 8802, 11310, 27498, 17822, 34010, 11130, 39822, 49498, 78190, 22112, 65030, 60480, 103398, 6426, 30402, 55838, 79814, 48112, 128086, 97524, 177498, 17228, 67934, 98496, 149202, 58914, 165618, 140182, 246886, 1890, 11178, 27322, 36610, 35048, 88130, 60480, 113562, 24352, 90070, 117720, 183438, 57510, 167022, 150878, 260390, 7988, 39290, 76320, 107622, 71850, 188718, 140182, 257050, 30450, 118182, 166718, 254450, 94312, 267610, 230580, 403878, 20, 178, 702, 860, 1608, 3760, 2290, 4442, 2352, 8120, 9590, 15358, 3940, 11702, 11178, 18940, 2268, 10360, 18130, 26222, 14540, 39118, 30402, 54980, 4600, 18302, 27018, 40720, 16872, 47060, 39290, 69478, 1428, 8120, 18830, 25522, 22420, 56978, 39822, 74380, 13880, 51922, 69078, 107120, 34872, 100780, 90070, 155978, 3676, 18302, 36258, 50884, 35352, 92336, 67934, 124918, 16128, 62104, 86506, 132482, 47804, 136138, 118182, 206516, 552, 3760, 10870, 14078, 17180, 42022, 27498, 52340, 15820, 56978, 71502, 112660, 32448, 95240, 88130, 150922, 8204, 39118, 72642, 103556, 63648, 169024, 128086, 233462, 23472, 92336, 133274, 202138, 78916, 222242, 188718, 332044, 1960, 11702, 28998, 38740, 37992, 95240, 65030, 122278, 27348, 100780, 130990, 204422, 63380, 184318, 167022, 287960, 9612, 47060, 90770, 128218, 84460, 222242, 165618, 303400, 35000, 136138, 192762, 293900, 109848, 311320, 267610, 469082, 108, 860, 2990, 3742, 5920, 14078, 8802, 16960, 7280, 25522, 30798, 49040, 13092, 38740, 36610, 62258, 5656, 26222, 46818, 67384, 38652, 103556, 79814, 144718, 12828, 50884, 74626, 112682, 45824, 128218, 107622, 190016, 2660, 15358, 36342, 49040, 44508, 112660, 78190, 146342, 28752, 107120, 141590, 219958, 70600, 204422, 183438, 317260, 8208, 40720, 80170, 112682, 77240, 202138, 149202, 274100, 34300, 132482, 185418, 283600, 103332, 293900, 254450, 445018, 640, 4442, 13158, 16960, 21492, 52340, 34010, 64858, 20748, 74380, 92710, 146342, 41600, 122278, 113562, 194240, 11592, 54980, 101330, 144718, 87760, 233462, 177498, 323200, 31700, 124918, 180882, 274100, 107868, 303400, 257050, 452582, 3192, 18940, 46510, 62258, 60080, 150922, 103398, 194240, 42220, 155978, 203502, 317260, 99108, 287960, 260390, 449242, 14144, 69478, 134682, 190016, 126348, 332044, 246886, 452582, 53172, 206516, 291674, 445018, 165376, 469082, 403878, 707584]

def prod(data):
	ans = 1
	for v in data:
		ans *= v
	return ans

def comb(n, r):
	res = Fraction(1)
	for i in range(r):
		res *= Fraction(n - i, r - i)
	return res

def length(n):
	res = 0
	while n > 0:
		res += 1
		n //= 2
	return res

def dfs(mask, count, rest, size, n):
	den = prod(range(1, DN + 1))
	num = 0
	for i in range(1 << DN - 2):
		if mask & i == mask:
			num += DA[i]
	f = Fraction(num, den)
	if rest == 0:
		return f * comb(n - length(mask) + 1, size)
	else:
		ans = dfs(mask, count + 1, rest - 1, size, n) / (count + 1)
		mask = mask << 1
		ans += dfs(mask | 1, 1, rest - 1, size, n)
		mask = mask << 1
		ans += dfs(mask | 1, 1, rest - 1, size, n)
		ans += f * dfs(1, 1, rest - 1, size + 1, n - length(mask) + 1)
		return ans
lines = sys.stdin.readlines()
for line in lines:
	(K, N) = map(int, line.split(' '))
	f = dfs(1, 1, K - 1, 1, N - 2) * prod(range(1, K + 1))
	print('{0} / {1}'.format(f.numerator, f.denominator))


import itertools
from fractions import gcd, Fraction as frac
from functools import lru_cache, reduce

@lru_cache(maxsize=None)
def fac(n):
	return 1 if n < 2 else n * fac(n - 1)

def bf(k, n):
	(s, p, q) = ([0 for i in range(n - 1)], 0, fac(n))
	for a in itertools.permutations(range(n)):
		x = 0
		for i in range(1, n - 1):
			if (a[i] - a[i - 1]) * (a[i] - a[i + 1]) > 0:
				x += 1
		s[x] += 1
		p += x ** k
	return frac(p, q)

@lru_cache(maxsize=None)
def T(n, k):
	if k == 1:
		return 2
	if n < 2 or k < 1 or k >= n:
		return 0
	return T(n - 1, k) * k + 2 * T(n - 1, k - 1) + (n - k) * T(n - 1, k - 2)

def S(n, k):
	return T(n, k + 1)

@lru_cache(maxsize=None)
def f(n, k):
	return frac(sum([j ** k * S(n, j) for j in range(n - 1)]), fac(n))

def sample(k):
	for i in range(k + 1):
		yield (i + 15, f(i + 15, k))

def F(n, k):
	if n < 15:
		return f(n, k)
	ret = frac(0)
	for t in sample(k):
		if n == t[0]:
			return t[1]
		ret += t[1] * reduce(lambda x, y: x * y, [frac(n - s[0], t[0] - s[0]) for s in sample(k) if s[0] != t[0]])
	return ret
(k, n) = map(int, input().split())
ans = F(n, k)
print(str(ans.numerator) + ' / ' + str(ans.denominator))


def gcd(a, b):
	while b > 0:
		r = a % b
		a = b
		b = r
	return a
(k, n) = map(int, input().split())
if k == 1:
	ans = (n - 2) * 2
	t = gcd(ans, 3)
	ans //= t
	t = 3 // t
	print(ans, '/', t, sep=' ')
if k == 2:
	ans = n * n * 40 - n * 144 + 131
	t = gcd(ans, 90)
	ans //= t
	t = 90 // t
	print(ans, '/', t, sep=' ')
if k == 3:
	ans = -(n - 11) * (n - 12) * (n - 13) * 55064 // 6 + 77237 * (n - 10) * (n - 12) * (n - 13) // 2 - 104674 * (n - 10) * (n - 11) * (n - 13) // 2 + 137935 * (n - 10) * (n - 11) * (n - 12) // 6
	t = gcd(ans, 315)
	ans //= t
	t = 315 // t
	print(ans, '/', t, sep=' ')
if k == 4:
	ans = 5005261 * (n - 11) * (n - 12) * (n - 13) * (n - 14) // 24 - 2600771 * 3 * (n - 10) * (n - 12) * (n - 13) * (n - 14) // 6 + 11630701 * (n - 10) * (n - 11) * (n - 13) * (n - 14) // 4 - 477619 * (4725 // 135) * (n - 10) * (n - 11) * (n - 12) * (n - 14) // 6 + 221989 * (4725 // 45) * (n - 10) * (n - 11) * (n - 12) * (n - 13) // 24
	t = gcd(ans, 4725)
	ans //= t
	t = 4725 // t
	print(ans, '/', t, sep=' ')
if k == 5:
	mx = 31185
	ans = ans = -6257824 * (mx // 945) * (n - 11) * (n - 12) * (n - 13) * (n - 14) * (n - 15) // 120 + 119007074 * (mx // 10395) * (n - 10) * (n - 12) * (n - 13) * (n - 14) * (n - 15) // 24 - 584326396 * (n - 10) * (n - 11) * (n - 13) * (n - 14) * (n - 15) // 12 + 8709826 * (mx // 297) * (n - 10) * (n - 11) * (n - 12) * (n - 14) * (n - 15) // 12 - 4377992 * (mx // 99) * (n - 10) * (n - 11) * (n - 12) * (n - 13) * (n - 15) // 24 + 95960902 * (mx // 1485) * (n - 10) * (n - 11) * (n - 12) * (n - 13) * (n - 14) // 120
	t = gcd(ans, mx)
	ans //= t
	t = mx // t
	print(ans, '/', t, sep=' ')


def Gcd(a, b):
	if b == 0:
		return a
	return Gcd(b, a % b)

def P(K, N):
	(n, d) = (1, 1)
	if K == 1:
		(n, d) = (2 * (N - 2), 3)
	if K == 2:
		(n, d) = (40 * N ** 2 - 144 * N + 131, 90)
	if K == 3:
		(n, d) = (280 * N ** 3 - 1344 * N ** 2 + 2063 * N - 1038, 945)
	if K == 4:
		(n, d) = (2800 * N ** 4 - 15680 * N ** 3 + 28844 * N ** 2 - 19288 * N + 4263, 14175)
	if K == 5:
		(n, d) = (12320 * N ** 5 - 73920 * N ** 4 + 130328 * N ** 3 - 29568 * N ** 2 - 64150 * N - 5124, 93555)
	g = Gcd(n, d)
	return (n // g, d // g)
(K, N) = map(int, input().split())
(n, d) = P(K, N)
print('%d / %d' % (n, d))


import math

class Rational:

	def simplify(self):
		[self.num, self.den] = [self.num // math.gcd(self.num, self.den), self.den // math.gcd(self.num, self.den)]

	def __init__(self, num, den):
		self.num = num
		self.den = den
		self.simplify()

	def __add__(self, b):
		return Rational(self.num * b.den + self.den * b.num, self.den * b.den)

	def __mul__(self, b):
		return Rational(self.num * b.num, self.den * b.den)

	def __str__(self):
		self.simplify()
		return str(self.num) + ' / ' + str(self.den)

def printmat(a, n):
	for i in range(n):
		print(list(map(str, a[i])))
	print()

def matmul(a, b, n):
	toret = []
	for i in range(n):
		row = []
		for j in range(n):
			temp = Rational(0, 1)
			for k in range(n):
				temp += a[i][k] * b[k][j]
			row.append(temp)
		toret.append(row)
	return toret

def matpow(a, n, e):
	curr = e
	apow2 = a
	toret = []
	for i in range(n):
		row = []
		for j in range(n):
			row.append(Rational(1 if i == j else 0, 1))
		toret.append(row)
	while curr > 0:
		if curr % 2 == 1:
			toret = matmul(toret, apow2, n)
		apow2 = matmul(apow2, apow2, n)
		curr //= 2
	return toret
maxk = 5
factlist = [1]
for i in range(1, 20):
	factlist.append(factlist[-1] * i)
patterns = [(1, 3, 4), (2, 4, 10), (2, 5, 54), (3, 5, 32), (3, 6, 202), (3, 6, 202), (3, 7, 1532), (4, 6, 122), (4, 7, 906), (4, 7, 882), (4, 8, 7640), (4, 7, 906), (4, 8, 7616), (4, 8, 7640), (4, 9, 74512), (5, 7, 544), (5, 8, 4604), (5, 8, 4520), (5, 9, 44060), (5, 8, 4520), (5, 9, 42756), (5, 9, 42864), (5, 10, 464480), (5, 8, 4604), (5, 9, 43976), (5, 9, 42756), (5, 10, 462936), (5, 9, 44060), (5, 10, 462936), (5, 10, 464480), (5, 11, 5536752)]
statelist = dict()
statelist[0] = [0]
matsize = 1
for i in range(1, maxk + 1):
	statelist[i] = list(range(matsize + 2 * i, matsize - 1, -1))
	matsize += 2 * i + 1
mat = []
for i in range(matsize):
	mat.append([0] * matsize)
	for j in range(matsize):
		mat[i][j] = Rational(0, 1)
for i in range(maxk + 1):
	mat[statelist[i][0]][statelist[i][0]] = Rational(1, 1)
	for j in range(1, len(statelist[i])):
		mat[statelist[i][j - 1]][statelist[i][j]] = Rational(1, 1)
Stirling = dict()
Stirling[1] = dict({1: 1, 2: 1, 3: 1, 4: 1, 5: 1})
Stirling[2] = dict({1: 0, 2: 2, 3: 6, 4: 14, 5: 30})
Stirling[3] = dict({1: 0, 2: 0, 3: 6, 4: 36, 5: 150})
Stirling[4] = dict({1: 0, 2: 0, 3: 0, 4: 24, 5: 240})
Stirling[5] = dict({1: 0, 2: 0, 3: 0, 4: 0, 5: 120})
for pat in patterns:
	for i in range(maxk):
		for j in range(pat[0], maxk + 1 - i):
			mat[statelist[j + i][pat[1] - 1]][statelist[i][0]] += Rational(Stirling[pat[0]][j], factlist[j]) * Rational(pat[2], factlist[pat[1]])
[k, n] = list(map(int, input().split()))
thepow = matpow(mat, matsize, n)
print(thepow[statelist[k][0]][statelist[0][0]] * Rational(factlist[k], 1))


from functools import reduce, lru_cache
from fractions import Fraction
import math
from itertools import product, permutations
from collections import defaultdict

def a_kl(k):
	a = [1]
	for _ in range(k - 1):
		a = [1] + [(l + 2) * al + al1 for (l, (al, al1)) in enumerate(zip(a[1:], a))] + [1]
	return a

def prod(x):
	return reduce(lambda a, b: a * b, x, 1)

def factorial_power(n, k):
	return prod(range(n - k + 1, n + 1))

def power(n, k):
	a = a_kl(k)
	return sum((factorial_power(n, i + 1) * a for (i, a) in enumerate(a)))

def expectation(n, k):
	a = a_kl(k)
	return sum((S_k(n, i + 1) * a * math.factorial(i + 1) for (i, a) in enumerate(a)))

def good0(x):
	return x[1] > max(x[0], x[2]) or x[1] < min(x[0], x[2])

@lru_cache
def h(s):
	idx = [0]
	for d in s:
		idx.append(idx[-1] + d)
	idx = idx[1:]
	res = defaultdict(int)
	for p in permutations(range(sum(s, 0) + 2)):
		if p[0] < p[1]:
			continue
		if all((good0(p[i - 1:i + 2]) for i in idx)):
			res[p[0]] += 1
	return dict(res)

@lru_cache
def choose(n, k):
	if n < 0 or k > n:
		return 0
	return reduce(lambda a, b: a * Fraction(*b), zip(range(n - k + 1, n + 1), range(1, k + 1)), Fraction(1, 1))

def g(s):
	if len(s) > 2:
		(s1, s2) = (s[:2][::-1], s[2:])
		(n1, n2) = (sum(s1) + 1, sum(s2) + 1)
		(h1d, h2d) = (h(s1), h(s2))
		return 2 * sum((choose(n1 - k1 + n2 - k2, n1 - k1) * choose(k1 + k2, k1) * h1 * h2 for ((k1, h1), (k2, h2)) in product(h1d.items(), h2d.items())))
	else:
		return 2 * sum(((k + 1) * v for (k, v) in h(s).items()))

@lru_cache
def e(s):
	return Fraction(g(s), math.factorial(sum(s) + 3))

def split3(d):
	start = 0
	b = []
	for i in range(len(d)):
		if d[i] == 3:
			b.append(d[start:i])
			start = i + 1
	b.append(d[start:])
	return b

def ncases(n, blocks):
	lens = [sum(x) + 3 for x in blocks]
	return choose(n - sum(lens) + len(lens), len(lens))

def S_k(n, k):
	if k == 1:
		return Fraction(2 * (n - 2), 3)
	p = 0
	for d in product([1, 2, 3], repeat=k - 1):
		blocks = split3(d)
		p += ncases(n, blocks) * prod((e(s) for s in blocks))
	return p
(k, n) = map(int, input().split())
p = expectation(n, k)
print(p.numerator, '/', p.denominator)


import fractions

def solution(n, k):
	if k == 1:
		a = 2 * n - 4
		return fractions.Fraction(a, 3)
	if k == 2:
		a = 40 * n ** 2 - 144 * n + 131
		return fractions.Fraction(a, 90)
	if k == 3:
		a = 280 * n ** 3 - 1344 * n ** 2 + 2063 * n - 1038
		return fractions.Fraction(a, 945)
	if k == 4:
		n2 = n * n
		n3 = n2 * n
		n4 = n3 * n
		a = 2800 * n4 - 15680 * n3 + 28844 * n2 - 19288 * n + 4263
		return fractions.Fraction(a, 14175)
	if k == 5:
		n2 = n * n
		n3 = n2 * n
		n4 = n3 * n
		n5 = n4 * n
		a = 12320 * n5 - 73920 * n4 + 130328 * n3 - 29568 * n2 - 64150 * n - 5124
		return fractions.Fraction(a, 93555)
(k, n) = map(int, input().split())
print(' / '.join(str(solution(n, k)).split('/')))


import math

def f(n, d):
	g = math.gcd(n, d)
	n = n // g
	d = d // g
	print(str(n) + ' / ' + str(d))

def sol(N, K):
	if K == 1:
		return [(N - 2) * 2, 3]
	if K == 2:
		num = (40 * N - 144) * N + 131
		den = 90
		return [num, den]
	if K == 3:
		num = ((280 * N - 1344) * N + 2063) * N - 1038
		den = 945
		return [num, den]
	if K == 4:
		num = (((2800 * N - 15680) * N + 28844) * N - 19288) * N + 4263
		den = 14175
		return [num, den]
	if K == 5:
		num = ((((12320 * N - 73920) * N + 130328) * N - 29568) * N - 64150) * N - 5124
		den = 93555
		return [num, den]
(K, N) = list(map(int, input().split(' ')))
(num, den) = sol(N, K)
f(num, den)