##### Welcome to Subscribe On Youtube

# 3082. Find the Sum of the Power of All Subsequences

## Description

You are given an integer array `nums`

of length `n`

and a **positive** integer `k`

.

The **power** of an array of integers is defined as the number of subsequences with their sum **equal** to `k`

.

Return *the sum of power of all subsequences of*

`nums`

*.*

Since the answer may be very large, return it **modulo** `10`

.^{9} + 7

**Example 1:**

**Input: ** nums = [1,2,3], k = 3

**Output: ** 6

**Explanation:**

There are `5`

subsequences of nums with non-zero power:

- The subsequence
`[`

has,**1**,**2**]**3**`2`

subsequences with`sum == 3`

:`[1,2,`

and__3__]`[`

.__1__,__2__,3] - The subsequence
`[`

has,2,**1**]**3**`1`

subsequence with`sum == 3`

:`[1,2,`

.__3__] - The subsequence
`[1,`

has,**2**]**3**`1`

subsequence with`sum == 3`

:`[1,2,`

.__3__] - The subsequence
`[`

has,**1**,3]**2**`1`

subsequence with`sum == 3`

:`[`

.__1__,__2__,3] - The subsequence
`[1,2,`

has]**3**`1`

subsequence with`sum == 3`

:`[1,2,`

.__3__]

Hence the answer is `2 + 1 + 1 + 1 + 1 = 6`

.

**Example 2:**

**Input: ** nums = [2,3,3], k = 5

**Output: ** 4

**Explanation:**

There are `3`

subsequences of nums with non-zero power:

- The subsequence
`[`

has 2 subsequences with,**2**,**3**]**3**`sum == 5`

:`[`

and__2__,3,__3__]`[`

.__2__,__3__,3] - The subsequence
`[`

has 1 subsequence with,3,**2**]**3**`sum == 5`

:`[`

.__2__,3,__3__] - The subsequence
`[`

has 1 subsequence with,**2**,3]**3**`sum == 5`

:`[`

.__2__,__3__,3]

Hence the answer is `2 + 1 + 1 = 4`

.

**Example 3:**

**Input: ** nums = [1,2,3], k = 7

**Output: ** 0

**Explanation: **There exists no subsequence with sum `7`

. Hence all subsequences of nums have `power = 0`

.

**Constraints:**

`1 <= n <= 100`

`1 <= nums[i] <= 10`

^{4}`1 <= k <= 100`