Tổ Hợp Xu I

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho hệ thống tiền tệ gồm $n$ loại xu, mỗi loại có giá trị nguyên dương. Hãy đếm số cách khác nhau để tạo thành tổng $x$ từ các xu. Mỗi loại xu có thể được dùng không giới hạn số lần.

Hai cách được coi là khác nhau nếu thứ tự sử dụng xu khác nhau. Ví dụ $2 + 3$ và $3 + 2$ là hai cách khác nhau.

In ra kết quả theo modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $x$ : số loại xu và tổng cần tạo.

Dòng thứ hai chứa $n$ số nguyên $c_{1}, c_{2}, \dots, c_{n}$ : giá trị của các loại xu.

Dữ liệu ra

In ra số cách tạo thành tổng $x$ , modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq n \leq 100$
$1 \leq x \leq 10^{6}$
$1 \leq c_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
1 1 1	1	Chỉ có một cách: dùng xu $1$
1 1000000 1	1	Chỉ có một cách: dùng $10^{6}$ xu giá trị $1$

Bình luận

Không có bình luận tại thời điểm này.