Counting All Subsets

Difficulty: 1100 2000 ms 128 MB

math combinatorics

A set has N distinct elements. How many subsets does it have (including the empty set), modulo 10⁹+7?

Input: one integer N.

Output: 2^N mod 10⁹+7.

Constraints:

• 0 ≤ N ≤ 10¹⁸

Sample Tests

3

8

0

1

Read the Editorial