Problem Statement

Number of Restricted Compositions of N You are given a non-negative integer N and three distinct positive integers A , B , and C . Count the ordered compositions of N whose parts are chosen from {A, B, C} and in which no two consecutive parts are equal. Different orders count as different compositions. Print the count modulo 1,000,000,007 . Input Format The first line contains N , the target sum. The second line contains A . The third line contains B . The fourth line contains C . Output Format Print the number of valid ordered compositions modulo 1,000,000,007 . Constraints 0 ≤ N ≤ 100,000 1 ≤ A < B < C ≤ 100 Examples Example 1 Input: 4 1 2 3 Output: 3 Explanation: The valid compositions are 1 + 3 , 3 + 1 , and 1 + 2 + 1 . Example 2 Input: 5 2 3 4 Output: 2 Explanation: The valid compositions are 2 + 3 and 3 + 2 . Example 3 Input: 0 1 3 5 Output: 1 Explanation: The empty composition is the single valid composition of zero. Notes A composition is ordered, so A + B and B + A are d