Playlist Duration Combinations

You are given n songs, where each song has a duration given in minutes. Your task is to determine the number of distinct playlists you can form such that the total duration sums up exactly to k minutes. In each playlist, the same song can be used multiple times.

This problem can be solved using dynamic programming. Let \(dp[i]\) be the number of ways to achieve a total duration of \(i\) minutes. Initially, \(dp[0] = 1\) since there is exactly one way to form a playlist with duration 0 (by selecting no songs). For every song with duration \(d\), for every total time \(i\) from \(d\) to \(k\), update \(dp[i] = dp[i] + dp[i-d]\). Your answer will be \(dp[k]\).

Input Format: The first two numbers denote the integer values \(n\) (the number of songs) and \(k\) (the target duration in minutes), followed by \(n\) integers representing the duration of each song.

Output Format: Output a single integer representing the number of distinct playlists with a total duration of exactly \(k\) minutes.

Example:

Input:
3 4 1 2 3
Output:
4

</p>

inputFormat

The input is given via standard input (stdin) and consists of a single line containing integers separated by spaces. The format is:

n k duration1 duration2 ... duration_n

Where:

• n is the number of songs.
• k is the target duration in minutes.
• Each of the following n integers represents the duration of a song.

outputFormat

The output should be written to standard output (stdout) as a single integer, which is the number of distinct playlists that sum exactly to k minutes.

## sample

3 4 1 2 3

4