题目描述

小X最近看了亚瑟王的传说，幻想自己也能成为这样的传奇人物。在梦中，小X看到前方由近及远有$n$个高度互不相同且均为整数的台阶，其中最矮的高度为1，最高的高度为$n$。小X隐约听见有人在说话：“拔出此石中剑者，即为英格兰之王。”顺着声音的方向，小X看见了一把插在石缝中的装饰华美的剑。“莫非这就是……”小X跑过去，恨不得立刻将其拔出。然而，小X接近它时就会被弹开。刚刚的声音再次响起：“看到那些台阶了吗？要想拔出石中剑，首先要跨过那些台阶。你可以选择从任意一个台阶出发，每次向前跨越若干个台阶，但必须保证每次落脚的台阶都高于上一次落脚的台阶。为了展现王的姿态，你要让落脚的次数尽量多。”这可难不倒小X，他轻松地完成了任务，步伐在天空中划出了一道优美的弧线。“最后，你还要在心中默念一个数，才能得到石中剑的认可。记住自己刚才的轨迹了吗？你看那些台阶，其实都是虚幻的，可以任意改变顺序。石中剑需要你回答的是，那些台阶有多少种不同的排列方法，可以用你刚才的轨迹来完成之前的任务呢？”思考了许久，小X身上直冒汗。身为正义使者的你，想要帮助他在梦中成为英格兰之王。为此，你潜入了他的意识，得到了他刚才的轨迹。现在，你必须尽快得到答案，从而放入他的意识，使他通过石中剑的考验。

输入格式

第一行一个整数$n$。

第二行一个整数$k$，表示小X刚才轨迹落脚的次数。

第三行$k$个整数，表示这个轨迹依次落脚的台阶的高度。

$1 \leq n \leq 15$，答案小于 $2^{31}$

输出格式

第一行一个整数，表示答案

输入样例

5
3
1 3 4

输出样例

11

提示

11种排列分别为(1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3,4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3,4)。