Spaceship Navigation in n-Dimensional Space

Little X is piloting his spaceship and plans to travel through an \(n\)-dimensional space. In this space every point is represented as \((x_1, x_2, \dots, x_n)\) where every coordinate \(x_i\) is a positive integer.

To complete his journey, he must select \(c\) (with \(c \ge 2\)) points at which the spaceship will stop. These \(c\) points should satisfy the following conditions:

1. For each point, every coordinate \(x_i\) is a positive integer with \(x_i \le m_i\), where \(m_i\) is the upper bound for the \(i\)th coordinate.
2. If the points are denoted \(P_1, P_2, \dots, P_c\) with \(P_i = (x_{i,1}, x_{i,2}, \dots, x_{i,n})\), then for every consecutive pair \(P_i\) and \(P_{i+1}\) (\(1 \le i x_{i,j} \quad (1 \le j \le n). \]
3. There exists a line that passes through all the chosen points. In an \(n\)-dimensional space a line can be represented by \(2n\) real numbers \(p_1, p_2, \dots, p_n, v_1, v_2, \dots, v_n\). A point \((x_1,x_2,\dots,x_n)\) lies on this line if and only if there exists a real number \(t\) such that \[ x_i = p_i + t\,v_i, \quad \text{for } i=1,2,\dots,n. \]

Since the coordinates of each point are positive integers and must be within the bounds given by \(m_i\), it turns out that any set of \(c\) collinear points (with the strictly increasing condition in every coordinate) will form an arithmetic progression. In other words, if we denote the first point as \(X = (x_1, x_2, \dots, x_n)\) and the step (or difference) as \(d = (d_1, d_2, \dots, d_n)\) with every \(d_i \ge 1\), then the chosen points are

[ X,; X+d,; X+2d,; \dots, ; X+(c-1)d, ]

and the constraints on each coordinate become

[ x_i + (c-1)d_i \le m_i \quad \text{and} \quad 1 \le x_i \le m_i - (c-1)d_i, \quad d_i \ge 1. ]

Your task is to compute the number of different schemes that satisfy the requirements. As the answer may be very large, output the answer modulo 10007.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(c\) (with \(c \ge 2\)), where \(n\) denotes the dimension of space.
• The second line contains \(n\) integers \(m_1, m_2, \dots, m_n\), where \(m_i\) is the maximum allowed value for the \(i\)th coordinate.

outputFormat

Output a single integer: the number of valid schemes modulo 10007.

sample

2 2
3 4

18