CF997D Cycles in product

题意

给你大小为 ​的两棵树 ​，构造一张新图，该图中每一个点的编号为 。如果在 ​中， ​和 ​之间有边，那么在该图上，对于任意 ， 和 之间有边。同样，如果在 ​中， ​和​之间有边，那么在图上，对于任意 ， 和 之间有边
求这个图上长度为 的环有多少个，环可以不为简单环，起始点或方向不同的环视为不同的环

，答案对 取模.