← 返回题目列表

AtCoder · fuka_bintree

D. 二叉树

中文机器翻译题面 查看原题

说明 给出了

1上面写有两个数字的节点是 有n。这个 使用所有n节点创建二叉树。对于二叉树的定义,例如: 维基百科页面 参见等。

将树的权重定义为树中包含的数字的总和。如果树是空集,则它的权重为 假设0。

当以下条件成立时,树是安定:对于除叶子之外的所有节点,左子树和右子树的权重差的绝对值为a以上b以下说法正确。这里,以左孩子为根的子树(如果没有左孩子则为空集)称为左子树,同样以右孩子为根的子树称为右子树。

n节点值和 给定a,b,输出稳定二叉树的数量。然而,在计算二叉树的数量时, 区分所有n节点。另外,子节点顺序不同或者节点父子关系不同的情况也单独统计。

输入

输入由多个测试用例组成。输入的结尾由仅包含三个零的行指示。每个测试用例均按以下格式给出。

n a b
x_1…x_n
  • 1 ≦ n ≦ 13
  • 0 ≦ a,b ≦ 2000
  • 1 ≦ x_i ≦ 100

测试用例 写入1行中,3整数n,a,b。

测试用例 写入2行中,n整数 表示第x_i。x_i为i点处写入的数字。

每个文件的测试用例数量保证不超过20个。

输出

对于每个测试用例,在一行中输出满足条件的二叉树的数量。

示例输入

1 0 100
1
2 3 3
1 2
3 0 2
1 2 3
10 0 10
1 2 3 4 5 6 7 8 9 10
13 0 10
1 2 3 4 5 6 7 8 9 10 11 12 13
0 0 0

示例输出 由

1
0
6
164650496
213181735360