K Subarray Products

Chef has an array $A$ consisting of $N$ non-negative integers. Chef only likes **non-empty** subarrays having size **at most** $K$. The happiness Chef gets from a subarray is equal to the **product** of all its elements. Find the **sum of happiness** of all the subarrays Chef likes. Since the sum can be huge, print it modulo $M$. ### Input - The first line of input will contain a single intege