沉迷《原初幻想41》的冒险者Antinomy来到了紫水宫——红玉海海底的一座古老宫殿，翠水之民的公主红玉曾被困在这里，光之战士将她解决了出来，并鼓励她带领族人拥抱地面上的变化。

紫水宫附近有许多海沟，Antinomy骑着肥鸡飞的时候发现迷路了。海沟可以看成是一棵树状的结构，共有个结点，每个结点就是一个路口，叶子结点就是走不下去的死胡同路口。

Antinomy想在每个结点上放不同颜色的便携式以太之光水晶，共有种颜色，每种颜色的以太之光的数量都是无限的（生产系玩家有钱），为了摆脱迷路的困境，Antinomy希望对于树上每对结点和，如果到的最短距离小于，那么和上放的以太之光水晶必须是不同颜色的。

Antinomy想知道有多少种满足这个要求的方案，由于答案可能很大，所以请输出答案对取模的结果。

(a + b) % p = (a % p + b % p) % p 

(a - b) % p = (a % p - b % p) % p

(a * b) % p = (a % p * b % p) % p 

a ^ b % p = ((a % p)^b) % p 

((a+b) % p + c) % p = (a + (b+c) % p) % p 

((a*b) % p * c)% p = (a * (b*c) % p) % p

(a + b) % p = (b+a) % p

(a * b) % p = (b * a) % p

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p