luogu#P10594. BZOJ2445 最大团

    ID: 14535 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>O2优化中国剩余定理,CRTLucas 定理

BZOJ2445 最大团

题目背景

题目来自原 BZOJ,我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益,可联系我们。

题目描述

一个 nn 个点的无向图被叫做是一个 symmetric labeled cliquer,当且仅当该图的任意一个连通子图拥有相同的点数,并且任意一个连通子图都是完全图。

现有 mm 种颜色和所有含有 nn 个点且节点有标号的 symmetric labeled cliquer。我们需要将每个 symmetric labeled cliquer 都染上一种颜色,两个不同的 symmetric labeled cliquer 可以染相同颜色,求方案数对 10940110^9-401 取模的结果。

输入格式

第一行读入一个正整数 TT,表示数据组数。

接下来每行包含两个正整数 n,mn,m,含义如题所述。

输出格式

输出包含 TT 行,每行输出答案。

1
4 2
32

提示

数据保证,1T21\leq T\leq 21n,m2×1091\leq n,m\leq 2\times 10^9