Set - MarisaOJ: Marisa Online Judge

Given a sequence of

n

$n$ distinct positive integers

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \ldots, a_n$ , a set

S

$S$ is defined as a subset with the largest possible size from the set

{a_{1}, a_{2}, \dots, a_{n}}

$\{a_1, a_2, \ldots, a_n\}$ such that if

x

$x$ is in

S

$S$ , then

x + 1

$x + 1$ is not in

S

$S$ . **Objective**: Given

n

$n$ and the sequence

a

$a$ , determine the size of the set

S

$S$ and the number of distinct ways to choose

S

$S$ , modulo

10^{9} + 7

$10^9 + 7$ . #### Input - The first line contains two integers

n

$n$ and

m

$m$

(1 \leq n, m \leq 100)

$(1 \leq n, m \leq 100)$ . - The second line contains

n

$n$ positive integers

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \ldots, a_n$

(1 \leq a_{i} \leq 10^{6})

$(1 \leq a_i \leq 10^6)$ . #### Output - Output a single line containing two integers

k

$k$ and

c

$c$ , where

k

$k$ is the size of the set

S

$S$ and

c

$c$ is the number of distinct ways to choose the set

S

$S$ modulo

10^{9} + 7

$10^9 + 7$ . #### Example Input:

210012

$2 100 1 2$

Output:

12

$1 2$

#### Subtasks - **Subtask 1 (50 points)**:

a_{i} \leq 10

$a_i \leq 10$ . - **Subtask 2 (40 points)**:

n \leq 1000, a_{i} \leq 10^{6}

$n \leq 1000, a_i \leq 10^6$ . - **Subtask 3 (10 points)**:

n = 1

$n = 1$ (in this case, the input file contains only one line with two integers

n

$n$ and

m

$m$ ).

Topic

Others

Rating

2000

Solution (0)

Solution