Cho dãy số Fibonacci với F[0] = 1, F[1] = 1, F[n] = F[n - 1] + F[n - 2) với n>= 2. Hãy tính F[n) chia dư cho 10^9 + 7.

Đầu vào:

Dòng 1 là số bộ test T

T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0<=N<=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
1
2
3
4
5

Output:

1
2
3
5
8

Một con ếch đang đứng ở bậc thang số 0.

Mỗi lần, nó có thể nhảy lên 1 hoặc 2 bậc.

Hãy tính số cách khác nhau để con ếch có thể nhảy đến bậc thang số n.

Dữ liệu vào (Input)

Một số nguyên n (0 ≤ n ≤ 50).

Dữ liệu ra (Output)

In ra số cách để con ếch có thể nhảy đến bậc thang số n.

Ví dụ

Input

4

Output

5

Giải thích ví dụ:

Các cách nhảy đến bậc 4 là:

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

→ Có 5 cách.

Tính tổ hợp chập k của n theo công thức Pascal (sử dụng đệ quy)

Ràng buộc: ~0 < K \leq N \leq 30~

Input 01:

3 2

Output 01:

3

Input 02:

6 2

Output 02:

15

Input 03:

10 2

Output 03:

45

Vẫn là con ếch ở bài trước, nhưng lần này nó khỏe hơn, có thể nhảy 1, 2 hoặc 3 bậc mỗi bước. Hãy tính số cách để nó lên đến bậc N.

Dữ liệu vào:

Một số nguyên dương N.

Dữ liệu ra:

Số cách nhảy (kết quả có thể rất lớn, hãy in ra phần dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 10^5

Ví dụ:

Input:

3

Output:

4

Giải thích: (1+1+1), (1+2), (2+1), (3).

Cầu thang có N bậc. Con ếch có thể nhảy 1 hoặc 2 bậc. Tuy nhiên, có K bậc thang bị hỏng, nếu nhảy vào đó sẽ bị ngã. Hãy đếm số cách để ếch nhảy lên bậc N mà không chạm vào các bậc hỏng.

Dữ liệu vào:

Dòng 1: Hai số N và K.

Dòng 2: K số nguyên là vị trí các bậc thang bị hỏng.

Dữ liệu ra:

Số cách nhảy (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 10^5

Ví dụ:

Input:

5 1 
3

Output:

2

Để bước lên bậc thang thứ i, bạn phải trả một khoản phí là A[i]. Bạn có thể bắt đầu từ bậc 0 hoặc bậc 1. Mỗi lần bạn có thể leo lên 1 hoặc 2 bậc. Hãy tìm cách leo lên đỉnh cầu thang (vượt qua bậc cuối cùng N-1) sao cho tổng chi phí phải trả là nhỏ nhất.

Dữ liệu vào:

Dòng 1: Số nguyên N.

Dòng 2: N số nguyên A[0], A[1], ..., A[N-1].

Dữ liệu ra:

Chi phí nhỏ nhất.

Ràng buộc:

2 <= N <= 1000

0 <= A[i] <= 999

Ví dụ:

Input:

3 
10 15 20

Output:

15

Giải thích: Bắt đầu từ bậc 1 (phí 15), nhảy 2 bước vượt qua bậc 2 để lên đỉnh.

Cần lát kín một cái sân hình chữ nhật kích thước 2 x N bằng các viên gạch hình chữ nhật kích thước 1 x 2. Các viên gạch có thể đặt nằm ngang hoặc nằm dọc. Hỏi có bao nhiêu cách lát sân?

Dữ liệu vào:

Số nguyên N.

Dữ liệu ra:

Số cách lát (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 1000

Ví dụ:

Input:

3

Output:

3

Bạn có các loại tiền mệnh giá C[1], C[2], ..., C[N]. Hãy đếm xem có bao nhiêu cách để tạo ra số tiền S từ các loại tiền đó. Giả sử số lượng mỗi loại tiền là vô hạn.

Dữ liệu vào:

Dòng 1: N và S.

Dòng 2: Các mệnh giá tiền.

Dữ liệu ra:

Số cách đổi (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 100

1 <= S <= 1000

Ví dụ:

Input:

3 5 
1 2 5

Output:

4

Giải thích: (1+1+1+1+1), (1+1+1+2), (1+2+2), (5).