# 题意：

3个岛屿群，每个岛屿群有若干岛屿。现在要在岛屿之间连桥，桥的长度是1，规定2个属于相同岛屿群的岛屿的距离要大于等于3.

# 思路：

## 1008: [HNOI2008]越狱

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 8165  Solved: 3486
[Submit][Status][Discuss]

## Description

监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果

## Input

输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

## Output

可能越狱的状态数，模100003取余

2 3

6

## HINT

6种状态为(000)(001)(011)(100)(110)(111)

## hdu 4451 Dressing (计数，思维题)

http://acm.hdu.edu.cn/showproblem.php?pid=4451

## poj 1322 chocolate (指数型母函数 )

http://poj.org/problem?id=1322

## hdu 1028 Ignatius and the Princess III（整数拆分，母函数模板题）

http://acm.hdu.edu.cn/showproblem.php?pid=1028

http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html

## hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145

## codeforces #334 div 2 D.Moodular Arithmetic

http://codeforces.com/contest/604/problem/D

f(0)=0,对于其他的值，当f（x）确定时，f（k*x%p）也随之确定，那么把k*x%p看做新的x,f（k*k*x%p）也随之确定…相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r.

## HUST team contest #2 C Divisible Subsequences ||poj 3844 (剩余类)

a[i] 到 a[j]的和为 sum[j]-sum[i-1]

## codeforces 569 D. Symmetric and Transitive (组合数学　第二类斯特林数　贝尔数)

D. Symmetric and Transitive
time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Johnny has recently learned about set theory. Now he is studying binary relations. You’ve probably heard the term “equivalence relation”. These relations are very important in many areas of mathematics. For example, the equality of the two numbers is an equivalence relation.

A set ρ of pairs (a, b) of elements of some set A is called a binary relation on set A. For two elements a and b of the set A we say that they are in relation ρ, if pair , in this case we use a notation .

Binary relation is equivalence relation, if:

1. It is reflexive (for any a it is true that );
2. It is symmetric (for any ab it is true that if , then );
3. It is transitive (if  and , than ).

Little Johnny is not completely a fool and he noticed that the first condition is not necessary! Here is his “proof”:

Take any two elements, a and b. If , then  (according to property (2)), which means  (according to property (3)).

It’s very simple, isn’t it? However, you noticed that Johnny’s “proof” is wrong, and decided to show him a lot of examples that prove him wrong.

Here’s your task: count the number of binary relations over a set of size n such that they are symmetric, transitive, but not an equivalence relations (i.e. they are not reflexive).

Since their number may be very large (not 0, according to Little Johnny), print the remainder of integer division of this number by 109 + 7.

Input

A single line contains a single integer n (1 ≤ n ≤ 4000).

Output

In a single line print the answer to the problem modulo 109 + 7.

Sample test(s)
input

output

input

output

input

output

Note

If n = 1 there is only one such relation — an empty one, i.e. . In other words, for a single element x of set A the following is hold: .

If n = 2 there are three such relations. Let’s assume that set A consists of two elements, x and y. Then the valid relations are ,ρ = {(x, x)}, ρ = {(y, y)}. It is easy to see that the three listed binary relations are symmetric and transitive relations, but they are not equivalence relations.

## 贝尔数(集合的划分数目)

Bn基数n集合划分数目。集合S的一个划分是定义为S的两两不相交的非空子集的族，它们的并是S。例如B3 = 5因为3个元素的集合{abc}有5种不同的划分方法：
• {{a}, {b}, {c}}
• {{a}, {bc}}
• {{b}, {ac}}
• {{c}, {ab}}
• {{a, b, c}}

B0是1因为空集

## 2公式编辑

Stirling数S（n, k）是把基数为n的集划分为正好k个非空集的方法的数目。

## 3贝尔三角形编辑

(1) 第一行第一项是1（a_{1,1} = 1）

(2) 对于n>1，第n行第一项等同第n-1行最后一项。（

(3) 对于m,n>1，第n行第m项等于它左边和左上方的两个数之和。（