← 返回 optiver 的题目列表Count Ordered Sequences That Sum to n
类型：online_judge
Given a positive integer n and an array k of distinct positive integers, you may submit any number of orders sequentially. Each order size must be one of the values in k.
Count the number of distinct ordered sequences of orders whose total size is exactly n. Two sequences are different if their order differs. Return 0 if no such sequence exists.
Input Format
First line: two integers n and m, where m is the length of k.
Second line: m distinct positive integers representing k.
Output Format
Print one integer: the number of ordered order sequences summing to n.
Constraints
1 <= n <= 1000
1 <= m <= 100
1 <= k[i] <= 1000
Values in k are distinct.
The answer fits in a signed 64-bit integer.
Example 1
Input:
3 2
1 2
Output:
3
The valid sequences are [1,1,1], [1,2], and [2,1].
Example 2
Input:
3 2
2 4
Output:
0
Example
Input
3 2
1 2
Output
3