The professor is planning a heist, this time in England. He along with his team of robbers want to break into the Jewel House at the Tower of London to steal the Kohinoor.

He has done his research and found that the lock of the Jewel House is password encrypted. The password is of length len and it is in lowercase ['a'-'z']. From his research, the professor got to know that password have, p number of pairs (L, R) which signifies the starting and ending position of the substring and every such substring must be a palindrome.

Given the values, calculate how many times the robbers have to input the password to try all possible passwords.

As the answer can be large, print it modulus 1000000007 (1e9+7).

Example:

Input

len = 4

p=3

pairs are [[1.2]

12,3],

[3.4]

Output

28