对于一个 到 的排列 ,将 和 交换,需要的代价为 ,记 表示通过交换将排列 变成从小到大的排列,即 的最小代价。一个算法是用 来估算 。给出 到 的排列的前 个元素,求有多少个排列 满足条件 。
输入 和 ,表示 到 的排列,以及确定了前 个数。
接下来一行包含 个数,表示排列中确定的前 个数。
输出一行,表示有多少个排列满足条件,输出答案 。
样例输入
5 2 1 4
样例输出
3
对于 的数据,。