input
output
3 1 2 3 1 2 2
9 16 1024 25 274576 4761 8464 627264 1115136