I am a Good Sublist


Ted has been studying numeric lists (lists of positive integer numbers not necessary different and not necessary ordered). He has learned that a good sublist of a given list L is such sublist whose sum of elements is no greater than a given number M. A maximal good sublist is a good sublist S of L such that for every element x of L not in S if x is added to S it becomes not good. Ted wants to know how many maximal good sublists are there of a given list. Can you help him?
Note: A sublist S of a list L is a list obtained by removing some (maybe none or all) of the elements of the list L.


First line of input contains integers N and M separated by spaces. Second line of input contains N integers li, 1 ≤ i ≤ N the elements of the list separated by spaces. It is granted that 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000 and 1 ≤ li ≤ 1000.


Output in a single line the number of maximal good sublists modulo 1000000007 (109+7).

Example input:
3 10
5 3 6
Example output:
Time and memory limit:

  • 1s
  • 64MB

Problem source: Caribbean Online Judge