逛孙厝的贝贝
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

厦门的孙厝步行街是个繁华的小吃街道，街上开着n家小吃店，编号依次为1到n。因为孙厝步行街距离JMU很近，贝贝每天放学都会日常去逛街。今天贝贝身上带了k元，贝贝发现了一种幸福感最满的购物方式：
  1. 前期限制花费：让自己在编号为的小吃店限制花费，第i个小吃店最多花费w_i元。
  2. 后期不限制花费：在编号比m大的小吃店，花费的金额不做限制。
贝贝想知道自己有多少种花费方式，但是他是个菜狗，所以他没有办法解决这个问题，于是他就找到一个大佬（也就是你）帮忙。

输入描述:

第一行，包含三个正整数，分别表示小吃店的个数、有限制的小吃店个数以及总消费。

第二行，包含m个整数，依次表示w_1，w_2，，。

输出描述:

仅一行，为贝贝花费的方案数量，答案取模。
示例1

输入

复制 
4 2 3
1 2

输出

复制 
15

说明

15种方案依次为：
0, 0, 0, 3
0, 0, 1, 2
0, 0, 2, 1
0, 0, 3, 0
0, 1, 0, 2
0, 1, 1, 1
0, 1, 2, 0
0, 2, 0, 1
0, 2, 1, 0
1, 0, 0, 2
1, 0, 1, 1
1, 0, 2, 0
1, 1, 0, 1
1, 1, 1, 0
1, 2, 0, 0