1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
There are N buttons on the console. Each button needs to be pushed exactly once.
 Each time you may push several buttons simultaneously.
Assume there are 4 buttons. 
You can first push button 1 and button 3 at one time, 
then push button 2 and button 4 at one time. 
It can be represented as a string "13-24". 
Other pushing way may be "1-2-4-3", "23-14" or "1234". 
Note that "23-41" is the same as "23-14".
Given the number N your task is to find the number of different valid pushing ways.
输入
An integer N. (1 <= N <= 1000)
输出
Output the number of different pushing ways. 
The answer would be very large so you only need to output the answer modulo 1000000007.
样例输入
3
样例输出
13
思路：数据N有1000还像220一样用搜索绝对爆炸。N^2是可以接受的
用DP，但是递推关系不好找。
问题一：递推关系 
如果把按钮分几波按也规定一下就好找递推方程了。
dp[i][j]为一共有i个按钮分成j波按的方案数。(j>i时为0)
要找到i和i-1的关系无非就是往i-1的所有方案中多加个数字i。
一共分成j波按，i比i-1也就多了一个数，有两种情况：
①：波数没有增加，只是把i扔进了任意一波而已，也就是原来的波数就是j，有j种情况 。 
②：增加一个单独的波数只放数字i，所以原来的j-1波中,一共有j个空挡可以插入，也是j种情况。  
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX