Koishi бессознательно переставляет \(n\) чисел: \(1, 2, \ldots, n\).
Она считает перестановку \(p\) красивой, если \(s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]\). \([x]\) равно \(1\), если выполняется \(x\), или \(0\) в противном случае.
Для каждого \(k\in[0,n-1]\) она хочет знать количество красивых перестановок длины \(n\), удовлетворяющих \(k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]\).
Примечание
Пусть \(f(p)=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]\).
В первом наборе входных данных \([2,1]\) — единственная красивая перестановка. И \(f([2,1])=0\).
Во втором наборе входных данных красивые перестановки:
\([1,2,4,3]\), \([1,3,4,2]\), \([1,4,2,3]\), \([2,1,3,4]\), \([2,3,1,4]\), \([3,1,2,4]\), \([3,4,2,1]\), \([4,2,3,1]\), \([4,3,1,2]\). Первые шесть из них удовлетворяют \(f(p)=2\), а остальные удовлетворяют \(f(p)=1\).