In juvenile years, I used to innocently long for his company. But finally, it is only confusion left by him in my mind.

For a given permutation of integers in , we call a subsegment an interval  iff the difference between the maximum value and the mininum value in the subsegment equals to .

For a given interval , we call it a non-trivial interval iff .

A permutation could be in my mind, iff there is at least one non-trivial interval whose length is greater than .

I will give you , please tell me how many permutations could be in my mind, modulo .

The first line contains two integers  ().

Output a single line contains a single integer, indicating the answer modulo .

3 2

0

4 2

20

300 20

940881556

100000 1

123738250