题目内容

很久很久以前，有一个神秘的森林，这个森林里有一棵特殊的树，它被称为“魔法之树”。这棵树的每个节点都有一个权值，为 $0$ 或 $1$，而且它们之间存在着连接，形成了一颗有 $n$ 个节点的二叉树。

人们相信，这棵树里蕴含着无穷的魔法力量，因为每一条路径都可以被看作是一串二进制数，而这些二进制数可以组成无数的数字，代表着神秘的力量和秘密。

为了探寻这个魔法之树的秘密，有许多勇敢的冒险家来到这个森林，试图通过对这棵树的研究来揭示其神秘力量的本质。然而，他们面临的问题是，有多少条路径代表的二进制数在 $[l,r]$ 区间范围内？

塔子哥是一个来自遥远国度的数学家，他擅长解决这种数字问题。他在研究这棵树的过程中，发现了一种高效的算法，可以帮助寻找树中所有代表的二进制数，并且得到有多少条路径代表的二进制数在 $[l,r]$ 区间范围内？他希望你能帮助他实现这个算法，为神秘的魔法之树揭开更多的秘密。

(请注意: 路径长度至少为 $1$ ，例如，节点 $3$ 到节点 $3$ 虽然有一个权值，但并不是合法路径！)

输入描述

第一行输人三个正整数 $n$ ， $l$ ， $r$ ，用空格隔开。

第二行输入一个长度为 $n$ 的 01 串，第 $i$ 个字符代表 $i$ 号节点的权值。

接下来的 $n -1$ 行，每行输入两个正整数 $u$ 和 $v$ ，代表 $u$ 号节点和 $v$ 号节点有一条边连接。

$1 \le n \le 10^3$ ， $1\le u,v \le n$ ， $1\le l \le r \le 10^{14}$

输出描述

一个整数，代表合法的路径条数。

样例

输入

5 2 5
11010
1 2
1 3
2 4
2 5

输出

9