Число способов размена

Условие

В первой строке дано число номиналов n, во второй — n различных номиналов, в третьей — сумма S. Выведите, сколькими способами можно набрать сумму S монетами; каждый номинал можно брать любое число раз, порядок не важен (1+2 и 2+1 — один способ). Ответ выведите по модулю 10^9 + 7.

Примеры

3
1 2 5
5

4

1
2
3

0

Ограничения

• 1 ≤ n ≤ 50
• 1 ≤ номинал ≤ 1000
• 0 ≤ S ≤ 10^4