As a traveling salesman in a globalized world, Alan has always been on the move. He almost never stayed in the same town for more than a few years before his heart longed for somewhere new. But this latest town is his favorite so far — it's just so colorful. Alan recently moved to Colorville, a quaint city nestled between picturesque mountains. Here, Alan has finally decided to settle down and build a home — a beautiful, spacious house to call his own.
In Colorville, many residents own houses, each uniquely painted with a distinct pattern of colors so that no two houses look alike. Every wall is made up of exactly n \times n squares, each painted a specific color (windows and doors are also considered unique "colors"). The walls of these houses are arranged in the shape of a regular -gon, with a roof on top. According to the long-standing traditions of Colorville, the roofs symbolize unity among its citizens, so all roofs are painted the same color.

Naturally, Alan wants to follow this tradition to fit in with the community. But with so many possible design combinations, it's overwhelming! Can you help Alan determine how many unique house designs are possible? (Two designs are considered the same if one can be rotated to become the other.)
One line contains three integers , , and , where:
n~(1 \le n \le 500) is the side length of each wall, meaning each wall is composed of n \times n squares;
m~(3 \le m \le 500) is the number of corners (and walls) of the regular polygon;
c~(1 \le c \le 500) is the number of different colors available.
Print the number of distinct house designs. Since the result can be very large, print it modulo 10^9 + 7.
Example 1
Example 2