TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6447
  • 题目
  • P6447站队
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果老师让机房内的$N$名信竞队员去操场跑步。

    首先所有队员需要排成一行,但是同学们都忘记了果老师之前编排好的队形。

    庆幸的是每一位队员还记得在他左边的队员数量和在他右边的队员数量之差的绝对值。

    队员$i$记得的数值是$A_i$,即在队员$i$左边的队员数量与右边的队员数量之差的绝对值为$A_i$。

    果老师现在来按照队员们反馈的数值来编排队伍,但是可能的合法队伍编排方案很多,想让学习信竞的你帮果老师算一算一共有多少种合法的编排方案。

    输入格式

    输入包含两行。

    第一行包括两个正整数$N(1 \leq N \leq 10^5)$。

    第二行包括$N$个正整数$A_i(0 \leq A_i \leq N - 1)$。

    输出格式

    输出合法的编排方案数,因为答案可能很大,输出对$10^9+7$取模的结果。

    样例输入 1

    5
    2 4 4 0 2

    样例输出 1

    4

    样例输入 2

    7
    6 4 0 2 4 0 2

    样例输出 2

    0

    样例输入 3

    8
    7 5 1 1 7 3 5 3

    样例输出 3

    16

    提示

    对于样例一:

    有以下$4$种合法

    • \((2, 1, 4, 5, 3)\)
    • \((2, 5, 4, 1, 3)\)
    • \((3, 1, 4, 5, 2)\)