만화 대모 험 (hdu 2512)

오랫동안 알고리즘 을 연구 하 다 보 니 개인 적 인 문제 에 신경 쓸 겨를 이 없 었 고, BUAA ACM / ICPC 트 레이 닝 팀 의 잘 생 긴 남자 들 은 대부분 싱글 이 었 다.어느 날, 그들 은 기관실 에서 절묘 한 계획 인 '만화 모험' 을 상의 했다.이 계획 은 wf 가 가장 먼저 제기 한 것 이다. 계획 의 내용 은 자신의 연락 처 를 캠퍼스 만화 뒷면 에 쓴 다음 에 고의로 자신의 카드 를 어 딘 가 에 잃 어 버 렸 다 는 것 이다. (예 를 들 어 물 방, TD, 식당, 메 인 M..) 그들 은 MM 이 그들 이 잃 어 버 린 카드 를 보고 자발적으로 연락 할 수 있 기 를 바란다. 그러면 MM 에 게 밥 을 살 기회 가 있 을 것 이다.그들 은 자신의 캐릭터 를 거의 같은 책 에 끼 워 놓 고 책 을 캠퍼스 구석구석 에 잃 어 버 리 기로 했다.모두 가 이 절묘 한 계획 을 위해 잘 부 르 고 있 을 때, 모두 가 한 가지 문 제 를 생각 해 냈 다.한 장의 만화 만 있다 면 한 권 의 책 에 끼 워 넣 는 방법 밖 에 없다 는 것 은 분명 하 다.한 캐릭터 가 두 장 있 을 때 두 가지 선택 이 있다. 즉, 두 장의 한 캐릭터 를 한 권 의 책 에 끼 우거 나 다른 책 에 따로 끼 우 는 것 이다.세 장의 만화 가 있 을 때 그들 은 다섯 가지 선택 을 했다. 즉,  {A}, {B}, {C}}, {A, B}, {C}, {B, C}, {A}, {A, C}, {B}}, {A, B, C}}  이 사악 한 계획 의 주최자 wf 는 ACM 훈련 에 n 명의 잘 생 긴 남자 (즉 N 장의 만화 가 있다) 가 있다 면 이 만화 들 을 책 에 끼 우 는 방법 이 얼마나 다른 지 알 고 싶 어 한다. 
Input
여러 그룹의 데 이 터 를 포함 하고 첫 번 째 행동 n 은 다음 n 조 데이터 가 있 음 을 나타 낸다.다음 줄 마다 x 는 모두 x 장의 만화 가 있다 는 것 을 나타 낸다.（1≤x≤2000）. 
Output
각 그룹의 데이터 에 대해 한 줄 을 출력 합 니 다. 다른 방법 수 입 니 다. 이 수 는 매우 클 수 있 기 때문에 우 리 는 그것 을 1000 의 나머지 로 나 누 기만 하면 됩 니 다. 
Sample Input

4
1
2
3
100

Sample Output

1
2
5
751

문제 풀이: n 장 1 캐릭터 가 i 책 을 사용 할 때 m, i - 1 책 을 사용 할 때 방법 이 t 인 것 을 알 고 있다 면 n + 1 장의 카드 는 i 책 을 사용 해 n 의 i - 1 책 방법 을 바탕 으로 책 한 권 을 다시 사용 하거나 i 책 임 의 한 권 에 직접 끼 워 넣 을 수 있 기 때문에 n + 1 장의 카드 는 i 책 을 사용 할 때 m * i + t 이다.상태 전이 방정식 a [i] [j] = i * a [j - 1] + a [i - 1] [j - 1] 을 얻 을 수 있 습 니 다.i 는 i 책 이 필요 하 다 는 방법 을 나타 내 고 j 는 j 카드 가 있다 는 것 을 나타 낸다.실질 은 베 어 수 입 니 다.
코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include