【题目描述】

有一个厨师准备做n+m道菜。他会做的菜包括k种菜，从1到k编号。

现在，厨师要给每个客人分配不同的菜单（任意两个人的菜单需要保证不同）。一份菜单指从这n+m道菜中任取任意数量道菜（按照下标顺序选择），至少要有一道菜。两个菜单不同，当且仅当将两个菜单的每道菜的编号按顺序连在一起后，两个菜单组成的数字串不相同。他已经做完m道菜了，但由于时间紧迫，他想让你帮他决定后n道菜（从菜谱中挑选），使得能服务的客人最多。请你告诉他最多能服务多少个客人（做好的菜不会被消耗，可以在不同的菜单中使用）。

由于这个答案可能很大，你只需要输出其对10^9+7 取模的结果。

【输入格式】 ​ 输入共两行。

​ 第一行三个整数n,m,k 。

​ 第二行m个整数，表示已经做好的菜。

【输出格式】 ​ 输出一行一个整数，表示最多可以服务的客人人数对10^9+7取模的结果。 【样例输入】 2 3 2

1 3

【样例输出】

14