Description

小X最近看了亚瑟王的传说，幻想自己也能成为这样的传奇人物。在梦中，小X看到前方由近及远有n个高度互不相

同且均为整数的台阶，其中最矮的高度为1，最高的高度为n。小X隐约听见有人在说话：“拔出此石中剑者，即为

英格兰之王。”顺着声音的方向，小X看见了一把插在石缝中的装饰华美的剑。“莫非这就是……”小X跑过去，恨

不得立刻将其拔出。然而，小X接近它时就会被弹开。刚刚的声音再次响起：“看到那些台阶了吗？要想拔出石中

剑，首先要跨过那些台阶。你可以选择从任意一个台阶出发，每次向前跨越若干个台阶，但必须保证每次落脚的台

阶都高于上一次落脚的台阶。为了展现王的姿态，你要让落脚的次数尽量多。”这可难不倒小X，他轻松地完成了

任务，步伐在天空中划出了一道优美的弧线。“最后，你还要在心中默念一个数，才能得到石中剑的认可。记住自

己刚才的轨迹了吗？你看那些台阶，其实都是虚幻的，可以任意改变顺序。石中剑需要你回答的是，那些台阶有多

少种不同的排列方法，可以用你刚才的轨迹来完成之前的任务呢？”思考了许久，小X身上直冒汗。身为正义使者

的你，想要帮助他在梦中成为英格兰之王。为此，你潜入了他的意识，得到了他刚才的轨迹。现在，你必须尽快得

到答案，从而放入他的意识，使他通过石中剑的考验。

Format

Input

第一行一个整数n。

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

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

1 ≤ n ≤ 15，答案小于 2^31

Output

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

Samples

5
3
1 3 4

11

Limitation

/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)。