TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3845
  • 题目
  • P3845分礼物
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1000ms
    问题描述

    一颗圣诞树挂有很多礼物,每个礼物都挂在树的分叉点或树枝端点上。挂有礼物的
    点标记为 1,没挂礼物的标记为 0,现在要把这些礼物连同树枝分给小盆友(当然一个
    小盆友只能分一个礼物)需要把圣诞树剪成很多小树,且保证一棵小树上有一个礼物。 请你计算一下共有多少种不同的剪法方案数。由于答案比较大,只需输出对 1000000007
    取模即可。 

    输入格式

    第一行 n,表示树共有 n 个节点,从 0 开始编号。
    以下 2 到 n 行每行一个数,表示编号 i-1 的节点的父亲编号 第 n+1 行共 n 个数,若第 i 号节点有礼物,则为 1,否则为 0.
     

    输出格式

    一个整数,若无法保证一棵小树上有一个礼物输出 0. 

    样例输入




    1


    1 0 0 0 1 1 

    样例输出

    5

    提示

    对于 30%的数据:n<=10
    对于 70%的数据:n<=1000
    对于 100%的数据:n<=100000