P1497 Wooden Ox and Flowing Horse

Kongming created the Wooden Ox and Flowing Horse. > The “wooden ox” has a square belly and a curved head, one leg with four feet; the head goes into the collar, and the tongue is attached to the belly. When heavily loaded it travels less, suitable for large-scale use, not for small errands; a single unit travels several tens of li, while a group travels twenty li. Curved pieces make the ox’s head, paired pieces the ox’s legs, crosswise pieces the ox’s collar, turning pieces the ox’s feet, covering pieces the ox’s back, square pieces the ox’s belly, hanging pieces the ox’s tongue, curved pieces the ox’s ribs, carved pieces the ox’s teeth, upright pieces the ox’s horns, thin pieces the ox’s yoke, and “she” pieces the ox’s autumn axle. When the ox is facing up with double shafts: when a person walks six chi, the ox walks four steps. Carrying one year’s grain, it travels twenty li per day, and the person is not greatly fatigued. As for the dimensions of the “flowing horse”: rib length 3 chi 5 cun, width 3 cun, thickness 2 cun 2 fen, the same on left and right. The front axle hole “fenmo” is 4 cun from the head, with a diameter of 2 cun. The front leg hole “fenmo” is 2 cun, 4 cun 5 fen from the front axle hole, width 1 cun. The front bar hole is 2 cun 7 fen from the front leg hole, hole length 2 cun, width 1 cun. The rear axle hole is 1 chi 5 fen from the front bar “fenmo”, same size as the front. The rear leg hole is 3 cun 5 fen from the rear axle hole “fenmo”, same size as the front. The rear bar hole is 2 cun 7 fen from the rear leg hole “fenmo”; the rear load clamp is 4 cun 5 fen from the rear bar hole “fenmo”. The front bar length is 1 chi 8 cun, width 2 cun, thickness 1 cun 5 fen. The rear bar and equal boards, two square bags, thickness 8 fen, length 2 chi 7 cun, height 1 chi 6 cun 5 fen, width 1 chi 6 cun; each holds 2 hu 3 dou of rice. From the upper bar hole to the underside of the rib is 7 cun, the same front and rear. The upper bar hole is 1 chi 3 cun from the lower bar hole “fenmo”, hole length 1 cun 5 fen, width 7 fen; all eight holes are the same. The four legs, front and rear, are 2 cun wide and 1 cun 5 fen thick. The shape is like an elephant; the shoe length is 4 cun, diameter 4 cun 3 fen. The hole diameter is for the central three-legged bar; its length is 2 chi 1 cun, width 1 cun 5 fen, thickness 1 cun 4 fen, and the bar ears are the same. (Records of the Three Kingdoms, “Zhuge Liang Collection: Method for Making the Wooden Ox and Flowing Horse”). However, in practice it has a flaw: no two can be in the same row or the same column!

Kongming excitedly invited Pang Tong to visit. Intending to challenge him, Kongming placed $k$ Wooden Ox and Flowing Horse pieces on a large $n \times n$ tiled grid and painted them in colors. He asked Pang Tong to count how many different valid layout configurations there are.

First line: $n, k, h$ ($n \le 20$, $h$ is the number of colors). The next $h$ lines give the quantity of each color.

The total number of valid layouts.

No big integer is needed. Moreover, Kongming stipulates that the grid cannot be flipped; that is, if two layouts become the same after a flip, they are still counted as two. Translated by ChatGPT 5