পাইথনে m আকারের অ্যালফাবেট থেকে n দৈর্ঘ্যের স্ট্রিং তৈরি যেখানে প্যালিনড্রোমিক সাবস্ট্রিং নেই

আমাদের m সংখ্যক অক্ষর এবং আরেকটি মান n দেওয়া আছে। এই m অক্ষর থেকে लेकर n দৈর্ঘ্যের স্ট্রিং তৈরি করতে হবে যাতে স্ট্রিং-এ ১-এর চেয়ে বড় কোনো প্যালিনড্রোমিক সাবস্ট্রিং না থাকে। উত্তর যদি খুব বড় হয় তবে ১০⁹+৭ দিয়ে মডুলো করতে হবে।

উদাহরণ

ইনপুট: n = 2, m = 3

আউটপুট: 6

কারণ m = 3 হলে অ্যালফাবেট {x, y, z} হতে পারে। সম্ভাব্য স্ট্রিংগুলো: [xx, xy, xz, yx, yy, yz, zx, zy, zz]। কিন্তু [xx, yy, zz] বৈধ নয় কারণ এগুলোর প্যালিনড্রোমিক সাবস্ট্রিং আছে। তাই মোট ৬টি বৈধ স্ট্রিং।

সমাধান পদ্ধতি

1. p := 10⁹+7
2. যদি n == 1 হয়, তবে m % p রিটার্ন করুন।
3. যদি n == 2 হয়, তবে m * (m - 1) % p রিটার্ন করুন।
4. যদি m <= 2 হয়, তবে 0 রিটার্ন করুন।
5. অন্যথায় m * (m - 1) * ((m - 2)^(n - 2) mod p) mod p রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

def solve(n, m):
    p = 10**9 + 7
    if n == 1:
        return m % p
    if n == 2:
        return m * (m - 1) % p
    if m <= 2:
        return 0
    return m * (m - 1) * pow(m - 2, n - 2, p) % p

# টেস্ট
n = 2
m = 3
print(solve(n, m))  # আউটপুট: 6

ইনপুট

3, [1,2,3,4,1]

আউটপুট

6