آرایه‌های خوب

آرایه‌ی $a$ به طول $n$ را در نظر بگیرید که برای هر $1 \leq i \leq n$، $1 \leq a_i \leq n$ است. می‌گوییم آرایه‌ی $a$ خوب است، اگر آرایه‌ای مانند $b$ به طول $n$ وجود داشته باشد که برای هر $1 \leq i \leq n$، $1 \leq b_i \leq n$ باشد و آرایه‌ی $$ \langle a_1+b_1, a_2+b_2, \ldots, a_n+b_n \rangle $$ اکیداً صعودی باشد؛ یعنی برای هر $1 \leq i < n$ داشته باشیم $a_i+b_i<a_{i+1}+b_{i+1}$. تعداد آرایه‌های خوب به طول $n$ را با $G_n$ نشان می‌دهیم. در شش بخش اول، باقی‌مانده‌ی $G_n$ بر $\Delta$ را حساب کنید.

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

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

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

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

بخش چهارم (۱۱ نمره): $n=500$ است.

بخش پنجم (۱۸ نمره): $n=5000$ است.

بخش ششم (۲۲ نمره): $n=10^6$ است.

بخش هفتم (۱۵ نمره): باقی‌مانده‌ی $\displaystyle\sum_{n=1}^{10^6} G_n$ بر $\Delta$ را حساب کنید.