408519: GYM103176 L LRTB and TBRL

Chinese is one of the several languages that can be written and read in two directions: "Left-to-right, top-to-bottom" (LRTB), and "Top-to-bottom, right-to-left" (TBRL).

When reading in LRTB, texts are written row by row, and from left to right in each row. Reading starts from the topmost row to the bottommost row.

When reading in TBRL, texts are written column by column, and from top to bottom in each column. Reading starts from the rightmost column to the leftmost column.

For example, when reading the text above, in LRTB, it is "培正喇沙編程挑戰賽". In TBRL, it is "喇程賽正編戰培沙挑".

Lee Sin has learnt $$$N$$$ Chinese characters. He has a grid paper with $$$R$$$ rows and $$$C$$$ columns, and he wants to write one of the $$$N$$$ Chinese characters he knows in each of the $$$R\times C$$$ cells. To prevent the two reading directions LRTB and TBRL from bringing readers into confusion, Lee Sin plans to write in a way that readers can read the same content no matter they read in LRTB or TBRL.

Please find out the number of ways Lee Sin can fill the grid paper so that readers can read the same content no matter they read in LRTB or TBRL.

The only line contains three integers $$$N$$$, $$$R$$$ and $$$C$$$ ($$$1\le N\le 4762$$$, $$$1\le R, C\le 1000$$$).

A single integer, the number of ways Lee Sin can fill the grid paper so that readers can read the same content no matter they read in LRTB or TBRL. As the number may be large, please output it modulo $$$10^9+7$$$.

3 3 3

27

2 3 2

4

4 4 5

256

11 19 31

300916151

In Sample 2, assume the $$$N=2$$$ Chinese characters Lee Sin knows are "李" and "星". The four ways he can fill the grid paper are: ("李李李李李李", "李李星李星星" , "星星李星李李"and "星星星星星星")

In Sample 4, the answer is $$$61159090448414546291 \mod (10^9+7) = 300916151$$$