给定三个正整数 、 和 ，统计长度在 到 之间，元素大小都在 到 之间的单调不降序列的数量。输出答案对 取模的结果。

游戏中有 个剧情点，由 到 编号，第 个剧情点可以经过不同的支线剧情，前往 种不同的新的剧情点。当然如果为 ，则说明 号剧情点是游戏的一个结局了。

开始处在 号剧情点。任何一个剧情点都是从 号剧情点可达的。从任意剧情点出发，都不能再回到这个剧情点。要想回到之前的剧情点，唯一的方法就是开始新的游戏，回到 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间，看完所有不同的支线剧情。

众所周知，在有些省份（比如山东、河南），省选时使用 Windows 垃圾系统评测，而 Windows 下默认的系统栈非常小（只有 1M），这造成了有些 DFS 相关算法无法通过极端数据，而是发生『栈溢出』的错误。一种解决方法是使用非递归的 DFS。

线性筛法（欧拉筛法）可以在 的时间内获得 的所有素数。算法保证每个合数都会被它的最小质因子筛掉，所以复杂度是线性的。同时，我们可以利用这一特性，结合积性函数的性质，在 的时间内筛出一些积性函数的值。

对于给出的 个询问，每次求有多少个数对 ，满足 ，，且 ，函数为 和 的最大公约数。

求 ， 且 为质数的 数量。

给定一张 个点 条边的无向连通图，初始时 号点属于集合 ， 号点属于集合 。现在要将其他点划分进两个集合，并使得评分最高，评分方式如下：

1. 对于点 ，划给 集合得 分，划给 集合得 分；
2. 对于一条边 ，若它连接两个 集合点，则得 分，若它连接两个 集合点，则得 分，否则将扣除 分。

监狱有连续编号为 的 个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

给定 个三元组 ，定义 当且仅当 且 且 。求 的最长上升子序列长度。

有两棵点集相同的树，顶点编号为 ，每个点都有一个权值，你需要选择一个点集的子集，使得这个子集在两棵树上都是一个连通块。你要选出权值和最大的子集，你只需要输出最大的权值和。