Max Heap is a special kind of complete binary tree in which for every node the value present in that node is greater than the value present in it's children nodes.

Find the number of distinct Max Heap can be made from A distinct integers.

In short, you have to ensure the following properties for the max heap :

Heap has to be a complete binary tree ( A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.)

Every node is greater than all its children.

NOTE: If you want to know more about Heaps, please visit this link. Return your answer modulo 109 + 7.

Problem Constraints

1 <= A <= 100

Input Format

First and only argument is an inetegr A.

Output Format

Return an integer denoting the number of distinct Max Heap.

Example Input

Input 1:

A = 4

Input 2:

A = 10

Example Output

Output 1:

3

Output 2:

3360

Please note that python code for above question should pass large test cases, and all corner test cases, reasoning for below MCQs is also needed, please dont copy (unhelpful if copied or didn't answer all)

1. Which of these about a frozenset is not true?

a) Mutable data type

b) Allows duplicate values

c) Data type with unordered values

d) Immutable data type

2. What is the syntax of the following Python code?

>>> a=frozenset(set([5,6,7]))

>>> a

a) {5,6,7}

b) frozenset({5,6,7})

c) Error, not possible to convert set into frozenset

d) Syntax error

3. Is the following Python code valid?

>>> a=frozenset([5,6,7])

>>> a

>>> a.add(5)

a) Yes, now a is {5,5,6,7}

b) No, frozen set is immutable

c) No, invalid syntax for add method

d) Yes, now a is {5,6,7}

4. Set members must not be hashable.

a) True

b) False

5. What will be the output of the following Python code?

>>> a={3,4,5}

>>> a.update([1,2,3])

>>> a

a) Error, no method called update for set data type

b) {1, 2, 3, 4, 5}

c) Error, list can't be added to set

d) Error, duplicate item present in list

6. What will be the output of the following Python code?

>>> a={1,2,3}

>>> a.intersection_update({2,3,4,5})

>>> a

a) {2,3}

b) Error, duplicate item present in list

c) Error, no method called intersection_update for set data type

d) {1,4,5}

7. What will be the output of the following Python code?

>>> a={1,2,3}

>>> b=a

>>> b.remove(3)

>>> a

a) {1,2,3}

b) Error, copying of sets isn't allowed

c) {1,2}

d) Error, invalid syntax for remove

8. What will be the output of the following Python code?

>>> a={1,2,3}

>>> b=a.copy()

>>> b.add(4)

>>> a

a) {1,2,3}

b) Error, invalid syntax for add

c) {1,2,3,4}

d) Error, copying of sets isn't allowed

9. What will be the output of the following Python code?

>>> a={1,2,3}

>>> b=a.add(4)

>>> b

a) 0

b) {1,2,3,4}

c) {1,2,3}

d) Nothing is printed

10. What will be the output of the following Python code?

>>> a={1,2,3}

>>> b=frozenset([3,4,5])

>>> a-b

a) {1,2}

b) Error as difference between a set and frozenset can't be found out

c) Error as unsupported operand type for set data type

d) frozenset({1,2})