0x30数学知识（0x37 容斥原理与Möbius函数）例题1：Devu and Flowers

题目描述

有 $n$ 个花瓶，第 $i$ 个花瓶里有 $f_i$ 朵花。他现在要选择 $s$ 朵花。

你需要求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量不同。

输入格式

第一行两个整数 $n \ s \ ( 1 \le n \le20 , 0 \le s \le 10^{14} )$ 。

下来 $n$ 个整数 $f_i \ (0 \le f_i \le 10^{12})$ 。

输出格式

一行一个整数， 答案对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

2 3
1 3

输出 #1

2

输入输出样例 #2

输入 #2

2 4
2 2

输出 #2

1

输入输出样例 #3

输入 #3

3 5
1 3 2

输出 #3

3

说明/提示

Sample 1. There are two ways of selecting $3$ flowers: ${1,2}$ and ${0,3}$ .

Sample 2. There is only one way of selecting $4$ flowers: ${2,2}$ .

Sample 3. There are three ways of selecting $5$ flowers: ${1,2,2}$ , ${0,3,2}$ , and ${1,3,1}$ .