Quy hoạch động Trạng thái

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Xếp hàng 100 (p) 1.0s 512M
2 Đèn trang trí 100 (p) 1.0s 512M
3 Xếp quân xe 100 (p) 1.0s 512M
4 Chăn Chối 100 (p) 1.0s 512M
5 Chọn ô 100 (p) 1.0s 512M
6 CSES - Counting Tilings | Đếm cách lát gạch 100 (p) 1.0s 512M

1. Xếp hàng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

2. Đèn trang trí

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

3. Xếp quân xe

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

4. Chăn Chối

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

5. Chọn ô

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

6. CSES - Counting Tilings | Đếm cách lát gạch

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hãy đếm số cách lấp đầy một lưới \(n \times m\) bằng cách sử dụng các viên gạch \(1 \times 2\) và \(2 \times 1\).

Input

  • Dòng đầu vào duy nhất chứa hai số nguyên \(n\) và \(m\).

Constraints

  • \(1 \leq n \leq 10\)
  • \(1 \leq m \leq 1000\)

Output

  • In một số nguyên: số lượng cách lát, chia lấy dư cho \(10^9 + 7\).

Example

Test 1

Input 
4 7
Output 
781