Preparando MOJI
You are given an array $$$a$$$ consisting of $$$n$$$ distinct positive integers.
Let's consider an infinite integer set $$$S$$$ which contains all integers $$$x$$$ that satisfy at least one of the following conditions:
For example, if $$$a = [1,2]$$$ then the $$$10$$$ smallest elements in $$$S$$$ will be $$$\{1,2,3,4,5,7,8,9,11,12\}$$$.
Find the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Since this number may be too large, print it modulo $$$10^9 + 7$$$.
The first line contains two integers $$$n$$$ and $$$p$$$ $$$(1 \leq n, p \leq 2 \cdot 10^5)$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
It is guaranteed that all the numbers in $$$a$$$ are distinct.
Print a single integer, the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Remember to print it modulo $$$10^9 + 7$$$.
2 4 6 1
9
4 7 20 39 5 200
14
2 200000 48763 1000000000
448201910
In the first example, the elements smaller than $$$2^4$$$ are $$$\{1, 3, 4, 6, 7, 9, 12, 13, 15\}$$$.
In the second example, the elements smaller than $$$2^7$$$ are $$$\{5,11,20,23,39,41,44,47,79,80,83,89,92,95\}$$$.
Informação
Provedor Codeforces
Código CF1635D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:22:05
Relacionados