Ramesses二世刚刚获胜归来。为了纪念这一胜利，他决定建造一座壮观的花园。这个花园里的植物排成一行，从他在Luxor的宫殿直达Karnak的神庙。所种植的植物只有莲花和纸莎草，因为它们分别代表上埃及和下埃及。
这个花园中必须有N棵植物，并且必须保持平衡，即在花园中任取一段，其中莲花和纸莎草的棵数之差不能超过2。
花园可以被表示为由字母L（莲花）和P（纸莎草）组成的字符串。例如，当N等于5时，有14种可能的平衡花园，按照字母排序如下：LLPLP，LLPPL，LPLLP，LPLPL，LPLPP， LPPLL，LPPLP，PLLPL，PLLPP，PLPLL，PLPLP，PLPPL，PPLLP 和 PPLPL。
给定长度的所有可能的平衡花园可按字母顺序排序，并从1开始编号。例如，当N等于5时，第12号花园是PLPPL。
任务
写一个程序，给定植物棵数N和一个表示平衡花园的字符串，计算该花园的序号模M的结果，其中M是一个给定的整数。
注意，在问题求解中，数值 M 除了简化计算外没有其他的作用。
限制
1 <= N <= 1,000,000
7 <= M <= 10,000,000
评分
有总分40分的测试点的N不超过40。
BZPRO