بلوک‌های هم‌قله

دو عدد صحیح مثبت $n$ و $m$ داده شده‌اند. تمام دنباله‌های به طول $n$ را که اعضایشان از مجموعه‌ی $ \{1,2,\ldots,m\} $ انتخاب شده‌اند، در نظر بگیرید. اعضای یک دنباله لزوماً متمایز نیستند و می‌توانند با یکدیگر برابر باشند.

روی هر دنباله می‌توان عملیات زیر را به تعداد دلخواه انجام داد: سه اندیس $\ell,r,s$ را که $$ 1\leq \ell\leq r<s\leq n $$ هستند انتخاب کنید، به‌طوری‌که دو بلوک مجاور $$ A_\ell,A_{\ell+1},\ldots,A_r \qquad\text{و}\qquad A_{r+1},A_{r+2},\ldots,A_s $$ بیشینه‌ی یکسانی داشته باشند؛ یعنی $$ \max_{\ell\leq i\leq r} A_i = \max_{r+1\leq j\leq s} A_j. $$ سپس جای این دو بلوک را عوض کنید. ترتیب عضوهای داخل هر بلوک تغییر نمی‌کند.

دنباله‌ها را به گروه‌هایی تقسیم می‌کنیم. دو دنباله در یک گروه قرار می‌گیرند اگر بتوان با انجام صفر یا چند عملیات، یکی را به دیگری تبدیل کرد. تعداد گروه‌های حاصل از تمام $m^n$ دنباله را با $C$ نشان دهید. مقدار $C\bmod\Delta$ را چاپ کنید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

بخش اول (۷ نمره): $n=2$ و $m=3$ است.

بخش دوم (۱۸ نمره): $n=7$ و $m=4$ است.

بخش سوم (۱۵ نمره): $n=600$ و $m=2$ است.

بخش چهارم (۳۱ نمره): $n=600$ و $m=100$ است.

بخش پنجم (۲۹ نمره): $n=1000$ و $m=10^6$ است.