题目描述

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

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

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

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

输入描述

第一行输人三个正整数$n,l,r(1 \le n \le 10^3,1\le l \le r \le 10^{18})$，用空格隔开。

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

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

输出描述

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

样例

输入

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

输出

9

说明