线段树分治，用可撤销并查集维护连通块。然后 ExCRT 和 ExLucas 计算答案。