Count of Increasing Subsequences

Interview

Time limit1sMemory limit512 MB

Summary
Count the strictly increasing subsequences of length K in a sequence of N distinct values, reported modulo 1e9+7.
Level

Medium6 of 10

Topics
Dynamic programming, Binary search, Prefix sum, Array
Solved
No attempts yet

Problem

Given a sequence A of size N and an integer K, count the increasing subsequences of A whose length is K.

Input

The first line contains N and K. The second line contains the sequence A1, A2, ..., AN.

Output

On the first line, print the number of increasing subsequences of A whose length is K, modulo 109+7.

Constraints

  • 1 ≤ N ≤ 100,000
  • 1 ≤ K ≤ 10
  • 1 ≤ Ai ≤ N
  • All Ai are distinct.

Examples5

  1. Example 1

    Input
    5 1
1 2 3 5 4
    Expected output
    5

  2. Example 2

    Input
    5 2
1 2 3 5 4
    Expected output
    9

  3. Example 3

    Input
    5 3
1 2 3 5 4
    Expected output
    7

  4. Example 4

    Input
    5 4
1 2 3 5 4
    Expected output
    2

  5. Example 5

    Input
    5 5
1 2 3 5 4
    Expected output
    0