def quick_pow(base, exponent, mod):
    """
    快速幂取模：计算 (base^exponent) % mod
    base: 底数
    exponent: 指数
    mod: 模数
    """
    result = 1                     # 最终结果，初始化为1
    base = base % mod              # 先对底数取模，防止一开始就太大
    while exponent > 0:            # 当指数还大于0时，继续处理
        # 检查 exponent 的最低位（二进制最后一位）是不是1
        if exponent & 1:           # 如果最低位是1，说明需要乘上当前的base
            result = (result * base) % mod   # 乘上去，并取模
        # 把 base 平方，准备下一次跳跃
        base = (base * base) % mod           # base -> base^2 -> base^4 -> base^8 …
        # 把 exponent 右移一位（相当于除以2，丢掉最低位）
        exponent >>= 1                       # 相当于 exponent = exponent // 2
    return result

# 测试一下：计算 2^10 对 1000 取模
print("2^10 mod 1000 =", quick_pow(2, 10, 1000))   # 输出 24，因为 2^10=1024，1024%1000=24

# 快速幂完整测试
def quick_pow(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent >>= 1
    return result

# 计算几个例子
print("2^10 mod 1000 =", quick_pow(2, 10, 1000))        # 24
print("3^5 mod 100 =", quick_pow(3, 5, 100))           # 3^5=243, 243%100=43
print("5^0 mod 7 =", quick_pow(5, 0, 7))               # 1
print("100^50 mod 9999 =", quick_pow(100, 50, 9999))   # 试一试

       0 （老祖宗）
      / \
     1   2
    / \   \
   3   4   5
          /
         6

# 定义树的父节点数组：parent[node] 表示 node 的直接父节点，根节点0的父节点设为-1
parent = [-1, 0, 0, 1, 1, 2, 2]   # 节点1、2的父亲是0；3、4的父亲是1；5、6的父亲是2

# 节点总数
N = 7

# 计算log2(N)向上取整，作为跳跃的最大指数
import math
MAX_LOG = int(math.log2(N)) + 1    # 因为2^3=8≥7，所以MAX_LOG=3+1=4更保险，也可以直接设为3

# 1. 构建倍增表 up[node][k] 和深度数组 depth[node]
up = [[-1] * MAX_LOG for _ in range(N)]   # up[node][k]：node的第2^k级祖先
depth = [0] * N                           # 每个节点的深度

# 初始化 up[node][0] = parent[node]
for node in range(N):
    up[node][0] = parent[node]

# 用BFS计算每个节点的深度（从根节点0开始）
from collections import deque
queue = deque()
queue.append(0)          # 根节点入队
depth[0] = 0             # 根节点深度为0
order = [0]              # 记录BFS遍历顺序（也可以先知道父节点再填子节点）

# 构建树的邻接表（用于BFS）
children = [[] for _ in range(N)]
for node in range(1, N):
    p = parent[node]
    if p != -1:
        children[p].append(node)

while queue:
    cur = queue.popleft()
    for child in children[cur]:
        depth[child] = depth[cur] + 1   # 子节点深度 = 父节点深度 + 1
        queue.append(child)

# 计算 up 表中 k>=1 的值（需要按深度从小到大的顺序填充）
# 由于子节点的深度大于父节点，我们可以直接按节点编号顺序，但最好按照BFS顺序或按深度排序
# 简单起见，我们按节点编号从小到大填充（假设父节点编号小于子节点时可用，但我们树中父节点确实小于子节点）
for k in range(1, MAX_LOG):
    for node in range(N):
        if up[node][k-1] != -1:               # 如果跳2^(k-1)步后位置存在
            up[node][k] = up[ up[node][k-1] ][k-1]  # 再跳2^(k-1)步
        else:
            up[node][k] = -1                  # 否则不存在

# 2. 实现LCA函数
def lca(x, y):
    # 步骤1：让深度较深的节点先跳到和另一个节点同一深度
    if depth[x] < depth[y]:
        x, y = y, x          # 确保x是较深的节点
    # 把x往上跳 depth[x] - depth[y] 步
    diff = depth[x] - depth[y]
    k = 0
    while diff:
        if diff & 1:         # 如果diff的二进制最低位是1，就跳2^k步
            x = up[x][k]
        diff >>= 1
        k += 1
    # 现在 x 和 y 在同一深度
    if x == y:
        return x             # 如果已经是同一个节点，那它本身就是LCA

    # 步骤2：从大到小尝试两个节点一起往上跳
    for k in range(MAX_LOG-1, -1, -1):
        if up[x][k] != up[y][k]:   # 如果跳完后祖先不同，说明还没到LCA，可以跳
            x = up[x][k]
            y = up[y][k]
    # 循环结束后，x和y的父亲就是LCA
    return up[x][0]

# 3. 测试几个查询
print("节点3和节点5的LCA是:", lca(3, 5))   # 预期0
print("节点3和节点4的LCA是:", lca(3, 4))   # 预期1
print("节点5和节点6的LCA是:", lca(5, 6))   # 预期2
print("节点0和节点5的LCA是:", lca(0, 5))   # 预期0（一个节点是根节点时，LCA就是根）

节点3和节点5的LCA是: 0
节点3和节点4的LCA是: 1
节点5和节点6的LCA是: 2
节点0和节点5的LCA是: 0