Initialization of an array#3906
Sign in

Initialization of an array

2 seconds
256 megabytes
Hard

In many programming languages, there are functions designed to fill an entire array or a portion of it with a specific value. In Pascal, this function is fillchar(), in Java it's Arrays.fill(), and in C++ it's memset(). In the new programming language J#, a function called mark() has been introduced, which is specifically for arrays of boolean type.

The mark function, when called with two parameters and , sets all elements of the array from index to inclusive to . For instance, consider an array of length , where elements are indexed starting from one and all values are initially . If you perform the operations mark(1, 3) and mark(2, 4), the entire array will be filled with values.

A common task for beginners learning J# is to write a program that uses exactly operations to completely fill an array of length with values, starting from an array filled with values.

You have quickly solved this task and are now curious: how many different ways can this be achieved? Two ways are considered different if, for at least one from to , the -th operation in the two programs uses different parameters. This number can be large, so it should be calculated modulo 10^9 + 7.

Input

The first line of the input contains two natural numbers and — the length of the array and the number of operations required in the program (1 \leq N, M \leq 70).

Output

Output a single line with the remainder when the number of ways to fill an array of elements with values using operations is divided by 10^9 + 7.

Examples

Example 1

Loading
Loading

Note

The possible variants are:

  • mark(1, 1); mark(1, 2)

  • mark(1, 1); mark(2, 2)

  • mark(1, 2); mark(1, 1)

  • mark(1, 2); mark(1, 2)

  • mark(1, 2); mark(2, 2)

  • mark(2, 2); mark(1, 1)

  • mark(2, 2); mark(1, 2)