小美有一颗节点编号为 1 n 的树，每个节点只有 \0,1 这两种值之一。 我们设 u → v 为节点 u 到节点 v 的简单路径。 g(u → v) 为从 u 开始到 v 结束的简单路径上经过的所有点（包括 u,v ）按照先后顺序组成的 01 字符串对应的十进制对 10^9+7 取模的结果。 例如，简单路径 u → v 经过所有节点组成的字符串为 01101 ，其对应十进制就是 13 ，因此 g(u → v) = 13 mod (10^9+7) = 13 。 小美会进行 m 次以下操作： 操作 1 ：将简单路径 u → v 上所有节点的值反置。 操作 2 ：询问 g(u → v) 的值。 你需要对小美的每一个操作二进行回答。 【反置】若当前字符为 0 ，反置后为 1 ；若当前字符为 1 ，反置后为 0 。
第一行输入两个整数 n,m(1 ≤ n,m ≤ 2 × 10^5) 表示树的大小以及 小美询问的次数。 第二行输入 n 个整数 a_i(a_i ∈ \0,1) 表示第 i 个节点初始的值。 接下来 n-1 行，每一行输入两个整数 u_i,v_i(1 ≤ u_i,v_i ≤ n) 表示节点 u_i 与 v_i 之间有一条边。 接下来 m 行，每一行输入三个整数 x,u,v(x ∈ \1,2,1 ≤ u,v ≤ n) ，具体的： x = 1 ：将简单路径 u → v 上所有节点的值反置。 x = 2 ：询问 g(u → v) 的值。
对于每个操作二，在一行上输出一个整数，表示 g(u → v) 的值。
5 5 0 0 0 0 0 1 2 1 3 2 4 2 5 2 1 4 1 1 3 2 4 1 1 2 5 2 5 1
0 1 7
考点：组合数学
数据规模 n ≤ 200000 ｜ 限制 3 秒 / 512MB ｜ 标准输入输出
参考方向：组合数学
用计数原理（加法/乘法原理）与组合数公式统计方案数。
思路框架（组合数学 通法 · 非本题专属）
实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。
复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例 1：输入 5 5 / 0 0 0 0 0 / 1 2 / 1 3 / 2 4 / 2 5 / 2 1 4 / 1 1 3 / 2 4 1 / 1 2 5 / 2 5 1 → 输出 0 / 1 / 7
第一次询问时得到的字符串为 000 ，第二次询问得到的字符串为 001 ，第三次询问得到的字符串为 111 。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2026年春招-美团-技术岗-第二批笔试；2026年春招-美团-算法策略岗-第二批笔试；2026年春招-美团-全栈岗-第二批笔试。