小 P 是个幼儿园老师。有一天，他组织 个小朋友玩游戏。游戏开始时，每个小朋友伸出两只手，没有手相互拉在一起。每次，小 P 等概率随机挑选两只空着的手，让这两只手拉在一起。小 P 一直重复这个操作，直到所有的手都拉在一起。小 P 在成为幼儿园老师之前是个数学专业的博士。因此，他想知道，当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少？其中，我们规定，一个小朋友左手拉右手的情况也形成一个圈。
由于小 P 忙着和小朋友们玩游戏，他找到了聪明的你，希望你能帮他解决这个问题。
输入数据仅一行，包含一个正整数 ，表示小朋友的数量。
输出文件仅一行，包含一个实数，表示当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少。输出和标准答案的绝对误差不能超过 。
大家都学过三角形吧。在这个问题里，我们要在随机图里数三角形。首先，我们有一张完全图G，它的边有可能是红色或者蓝色。其中有三种可能的随机性。
现在你需要找出三条边同色的三角形的期望。
第一行一个数 , 表示G的顶点个数。接下来 行，每行四或五个数字 ，表示点 和 点 之间的边的随机种类是 , 且它对应的概率为 。满足 且 是 到 的实数。保证每条边恰好出现一次。如果 ，则还会有一个输入 ,表示这条边属于那一组。如前面所述，同一组的所有边的概率加起来为 ，且恰好有一条为红色或蓝色。保证每组至少有两条边，且组的编号为从 开始的连续编号。
一行，一个数，表示同色三角形的期望个数，保留两位小数。
刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图 ，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说， 中每有一个三边颜色都互不同的三角形（异色三角形）可以得 分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉 分，其它三角形不得分也不扣分。
现在，请你写一个程序来计算 的多样性分数。
第一行两个正整数 和 ，其中 表示 中顶点的个数， 表示 中红色或者绿色的边的条数。
接下来 行每行包括三个整数 ，代表连接顶点 和顶点 的边颜色为红色 或者绿色 。
一行， 的多样性得分。
X 国的地图可以被看作一个两行 列的网格状图。现在 X 国需要修建铁路，然而该国的国王非常小气，他只想保证位于某两列之间的所有城市互相可以到达就行了，在此基础上，他希望所花费的代价最小。
铁路可以建在任何两个相邻的点之间，使他们可以互相到达。可以作为工作人员，你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。
对于 ：当前情况下，使第 列到第 列之间的所有城市连通的最小代价是多少（列下标从 开始）？注意不能用其他列的城市。
然而你还有更大的困难，随着时间变化，使用某些边作为铁路的代价会发生改变，你必须有效率地处理这些变化。
第一行两个正整数 ，表示该国有 行 列以及 个询问或者操作。
第二行 个数，前 个数依次表示在第一行的 条边上修建铁路的代价。
接下来 个数，依次表示在第二行的 条边上修建铁路的代价。
最后 个数，依次表示在第 列到第 列的边上修建铁路的代价。
接下来 行的输入具有如下形式，，其中
依次对每个询问，用一行输出相应的答案。
瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，每个战舰都可以看做一个点，在空间站中一共分布着 艘银河战舰。
玛德利德：“你说这些都是你的，那你让他们动一动啊”。
瑞奥：“诶你看,那艘动了！”。
玛德利德：“操作指令由我来发，一共有 种动的方法……”。
瑞奥：“我觉得这样有失公正……”。
第一行一个正整数 ，表示战舰的数量。
接下来 行，每行两个实数，代表第 个战舰的 坐标。
然后一个正整数 ，代表调度的次数。
接下来 行操作，每个操作都是如下类型的一种：
输出包括 行，代表着 艘战舰经过 次调度之后的坐标（保留两位小数）。
斐波那契数列定义如下：
给出个正整数，求对应的斐波那契数的最小公倍数，由于数字很大，输出模 的结果即可。
例如：, 对应的斐波那契数为：, 他们的最小公倍数为。
第行个数，表示数字的数量。（）。
第至行每行个数，对应。（)。
输出的结果。
去年的Lucas非常喜欢数论题，但是一年以后的Lucas却不那么喜欢了。
在整理以前的试题时，发现了这样一道题目“求,其中”，其中表示的约数个数。他现在长大了，题目也变难了。
求如下表达式的值：
其中表示的约数个数。
他发现答案有点大，只需要输出模的值。
第一行一个整数。
一行一个整数，表示答案模的值。
七夕祭上，牵着的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员、_和拯救出来的的。看到两人对太鼓达人产生了兴趣，果断闪人，于是拿起鼓棒准备挑战。然而即使是在普通难度下，的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。十分过意不去，决定帮助工作人员修鼓。
鼓的主要元件是个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用和表示。显然，从不同的位置出发沿顺时针方向连续检查个传感器可以得到个长度为的串。知道这个串应该是互不相同的。而且鼓的设计很精密，会取到可能的最大值。现在已经了解到了K的值，他希望你求出的值，并给出字典序最小的传感器排布方案。
一个整数。
一个整数和一个二进制串，由一个空格分隔。表示可能的最大的以及字典序最小的排布方案，字符表示关，表示开。你输出的串的第一个字和最后一个字是相邻的。
Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the from the west and the from the north as .
Joisino thinks that a touring plan is good if it satisfies the following conditions:
Let be the section where she starts the tour. Then, and hold.
Let be the section where she has lunch. Then, and hold.
Let be the section where she ends the tour. Then, and hold.
By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.
Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo .
Input is given from Standard Input in the following format:
Print the number of the different good touring plans, modulo .
Shinku is very interested in the set. One day, she got sets, and the number is in the set. But she doesn’t think it is interesting enough, so she applies magic to these sets. There are three kinds of magic:
But unfortunately, for some reason the type magic fails. So Shinku wants you to tell her the answer after every type magic.
Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.
The first line contains two integers , the number of initial sets and the number of the magic.
The second line contains integers. The number is the number in the set initially.
The next lines describe the sequence of magic. The line describes the magic. Each magic is a magic as described above.
For each type magic, output the answer you are asked to calculate.