$\text{Description}$
有一片景区有 $n$ 个景点，景点间的道路组成一棵 $n$ 个点的树，相邻景点间道路长度相同。有 $m$ 条观光路线，分别位于树上的路径 $(u_1,v_1),(u_2,v_2),\cdots,(u_m,v_m)$，第 $i$ 条观光路线上有 $a_i$ 辆互不相同的车。张三要跟随旅行团来到景区，旅行团的集合区域也是一条路径 $(s,t)$。张三想要依次坐 $K$ 趟车，每次可以选择任意路线上的任意一辆车。我们称景点 $t$ 在路径 $s$ （无论 $s$ 是观光路线还是集合区域）的服务范围内，当且仅当 $t$ 到 $s$ 上任意一点的距离都不超过 $s$ 的长度。称所有在服务范围内的景点的集合为一条路径的服务范围。他希望坐车的方案满足以下要求：
- 乘坐的每辆车所属观光路线的服务范围都包含集合区域的服务范围。
- 任何一个不在集合区域的服务范围内的景点都不会同时在乘坐的每辆车所属观光路线的服务范围内。
张三得知旅行团有 $q$ 套可能的集合区域 $(s_i,t_i)$，他希望你帮他计算出对于每种集合区域的方案，他可能的乘车方案数分别有多少。方案数对 $1000003$ 取模。