Circular Partitioning Game

Dingding is addicted to a number game. In this game, you are given a circle of n integers. You have to partition the circle into exactly m contiguous parts (segments) in the order they appear on the circle. For each segment, compute the sum of its numbers and then take that sum modulo 10. Note that the modulo operation always yields a non‐negative result, even for negative numbers. Finally, multiply together the m results to obtain a number k.

You are asked to compute either the maximum or minimum possible value of k based on the following input flag. For example, consider the circle with n = 4 and m = 2 with the numbers shown below:

When the goal is to minimize k, one possible partition is:
Segment 1: (2, -1) → ((2 + (-1)) mod 10 = 1)
Segment 2: (4, 3) → ((4 + 3) mod 10 = 7)
Result: 1 × 7 = 7.

When the goal is to maximize k, another partition could be:
Segment 1: (2, 4, 3) → ((2 + 4 + 3) mod 10 = 9)
Segment 2: (-1) → ((-1) mod 10 = 9)
Result: 9 × 9 = 81.

Your task is to help Dingding win the game by computing the required value.

Note: Since the numbers are arranged in a circle, you are allowed to choose any starting point for the partition, but the order of the numbers cannot change.

Mathematical Formulation:

Let the numbers be \(a_0, a_1, \ldots, a_{n-1}\) arranged in a circle. For a given starting index \(s\), let the rearranged sequence be \(b_0, b_1, \ldots, b_{n-1}\) where \(b_i = a_{(s+i) \bmod n}\). For any segment spanning indices \(i\) to \(j\) (inclusive), its value is defined as \[ V(i, j)=\left(\sum_{k=i}^{j} b_k\right) \bmod 10. \] If you partition the sequence into \(m\) segments, and denote the values of these segments as \(v_1, v_2, \ldots, v_m\), then \[ k = v_1 \times v_2 \times \cdots \times v_m. \] Depending on the input parameter, you are to output the maximum possible \(k\) or the minimum possible \(k\). In this problem, all modulo computations are defined such that the result is always nonnegative.

inputFormat

The first line contains three integers n, m, and t where n is the number of integers, m is the number of segments, and t is the target flag (1 for maximum and 0 for minimum).

The second line contains n space-separated integers representing the circle in order.

outputFormat

Output a single integer which is the maximum or minimum possible value of k as specified by the input flag.

sample

4 2 1
2 -1 4 3

81