{"problem":{"name":"Road of the King","description":{"content":"There are $N$ towns in Takahashi Kingdom. They are conveniently numbered $1$ through $N$. Takahashi the king is planning to go on a tour of inspection for $M$ days. He will determine a sequence of tow","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"codefestival_2016_final_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ towns in Takahashi Kingdom. They are conveniently numbered $1$ through $N$.\nTakahashi the king is planning to go on a tour of inspection for $M$ days. He will determine a sequence of towns $c$, and visit town $c_i$ on the $i$\\-th day. That is, on the $i$\\-th day, he will travel from his current location to town $c_i$. If he is already at town $c_i$, he will stay at that town. His location just before the beginning of the tour is town $1$, the capital. The tour ends at town $c_M$, without getting back to the capital.\nThe problem is that there is no paved road in this kingdom. He decided to resolve this issue by paving the road himself while traveling. When he travels from town $a$ to town $b$, there will be a newly paved one-way road from town $a$ to town $b$.\nSince he cares for his people, he wants the following condition to be satisfied after his tour is over: \"it is possible to travel from any town to any other town by traversing roads paved by him\". How many sequences of towns $c$ satisfy this condition?\n\n## Constraints\n\n*   $2≦N≦300$\n*   $1≦M≦300$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"codefestival_2016_final_f","tags":[],"sample_group":[["3 3","2\n\nAs shown below, the condition is satisfied only when $c = (2,3,1)$ or $c = (3,2,1)$. Sequences such as $c = (2,3,2)$, $c = (2,1,3)$, $c = (1,2,2)$ do not satisfy the condition.\n![image](https://atcoder.jp/img/code-festival-2016-final/199a3fd8d2aed75750901a206c8b7e76.png)"],["150 300","734286322"],["300 150","0"]],"created_at":"2026-03-03 11:01:13"}}