All the students (except the CR) are standing in a queue to submit their bills. The students have different seniority. In all, there are N students of K different seniority levels. These are given to you in an array, where A1, A2, ..., AN denote the seniority of students in the queue. AN denotes front of the queue and A1 denotes the end of the queue.

CR gets an interesting thought past his head. He begins to think what if every student starting from the end of the queue begins to delegate his job of submitting bills to a student least ahead of him in the queue but junior to him. The CR's fearfulness of this scenario is f = i2 - i1 + 1, where i1 is the index of a student in queue and i2 is the index of the junior student. CR's total fearfulness of chaos is the product of all the fearfulness in CR's mind. Note if a student has no junior ahead of him/her in the queue then CR's fearfulness for this student is 1.

You are required to find the CR's total fearfulness given an arrangement of students in a queue. Since this number can be quite large output it modulo 1000000007.

Input
Input description.

• The first line contains two integers N and K denoting the number of students and the number of seniority levels. The second line contains N space-separated integers A1, A2, ..., AN denoting the seniority of students in the queue. AN denotes front of the queue and A1 denotes end of the queue.

Output
Output description.

• Output a single integer denoting the total fearfulness of the CR

Constraints

• 1 ≤ N ≤ 1000000
• 1 ≤ A1, A2, ..., AN ≤ 1000000
• 2 ≤ K ≤ 100000