P7392 「TOCO Round 1」奇怪的排序
题目背景
欢喜不问天，风流不问天，温柔不问天，良辰不问天，良缘不问天。
问你不问天。
题目描述
情人节那天 $\color{orange}\texttt{Biadocy}$ 被虐得好惨，尤其是上流的公爵和小孩说什么《和你在一起的每一天，都叫情人节》。于是他找到了一个机会来报复。
现在有 $n$ 对情人编号为 $1\sim n$ 按任意顺序排成一列，$\color{orange}\texttt{Biadocy}$ 对他们执行了下面这段排序的伪代码。
$\color{orange}\texttt{Biadocy}$ 想知道有多少种初始排列满足按照这段伪代码排序后情人们的编号有序。也许这能让他好受一点。
输入格式
无
输出格式
无
说明/提示
对于前 $10\%$ 的数据，$T=0$。
对于前 $30\%$ 的数据，$T\leq 10$，$n\leq 7$。
对于另外 $10\%$ 的数据，$k=0$。
对于另外 $10\%$ 的数据，$k=100$。
对于 $100\%$ 的数据，$0\leq T\leq 10^5$，$1\leq n\leq 10^6$，$0\leq k\leq 100$。