This problem can be solved using the meet-in-the-middle trick.

It is known that, among the \(2 ^ N\) (not necessarily contiguous) subsequences of length \(N\), there are \(\operatorname{fib} _ N\) subsequences where no adjacent elements are picked, where \(\operatorname{fib} _ 0=1,\operatorname{fib} _ 1=2,\operatorname{fib} _ {i+2}=\operatorname{fib} _ {i+1}+\operatorname{fib} _ i\) (Fibonacci sequence).

Divide the given length-\(N\) sequence into the former half with \(\lfloor N/2\rfloor\) elements and the latter half with \(\lceil N/2\rceil\). Then, there are \(\operatorname{fib} _ {\lfloor N/2\rfloor}\) and \(\operatorname{fib} _ {\lceil N/2\rceil}\) subsequences of the respective half where no adjacent elements are picked. When \(N\le60\), we have \(\operatorname{fib} _ {\lfloor N/2\rfloor}\le\operatorname{fib} _ {\lceil N/2\rceil}\le2178309\), so we can calculate the sum, modulo \(M\), of the values contained in each of the \(\operatorname{fib} _ {\lfloor N/2\rfloor}\) and \(\operatorname{fib} _ {\lceil N/2\rceil}\) subsequences.

Using this information, the combinations of the two halves that sum to \(M\) can counted in a total of \(O(\operatorname{fib} _ {\lfloor N/2\rfloor}\log\operatorname{fib} _ {\lceil N/2\rceil})=O(N((1+\sqrt5)/2)^N)\) time.

This count excessively include a combination that picks the two elements around the boundary (the last element of the former half and the first of the latter), which needs to be eliminated. This extra count can also be found in the same algorithm, so the problem can be solved in a total of \(O(N((1+\sqrt5)/2)^N)\) time.

The sample code is shown below.

Note that some implementation may require to handle \(N=1\) as a special case (because one of the partition becomes empty).

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N, M;
    cin >> N >> M;
    vector<unsigned> A(N);
    for (auto&& a : A)
        cin >> a;

    // Enumerates the sums of all subsequences without adjacent picks
    // Also finds those that picks the last element
    const auto solve{[M](const auto& seq) -> pair<vector<unsigned>, vector<unsigned>> {
        vector<unsigned> used, unused;
        unused.emplace_back();
        for (const auto x : seq) {
            swap(used, unused);
            for (auto&& v : used) {
                unused.emplace_back(v);
                (v += x) %= M;
            }
        }
        vector<unsigned> all(used);
        ranges::copy(unused, back_inserter(all));
        ranges::sort(used);
        ranges::sort(all);
        return make_pair(used, all);
    }};

    // The result for the first half
    const auto [first_used, first_all]{solve(A | views::take(N / 2))};
    // The result for the second half
    const auto [second_used, second_all]{solve(A | views::reverse | views::take((N + 1) / 2))};

    unsigned long ans{};
    for (const auto a : first_all)
        ans += ranges::upper_bound(second_all, (M - a) % M) - ranges::lower_bound(second_all, (M - a) % M);

    // Subtract those picking both around the boundary
    for (const auto a : first_used)
        ans -= ranges::upper_bound(second_used, (M - a) % M) - ranges::lower_bound(second_used, (M - a) % M);

    cout << ans << endl;

    return 0;
}