Problem : https://atcoder.jp/contests/abc171/tasks/abc171_f

Ill explain my idea below with the first example.

_______ o ___________ o ________ f __________

we are able to place letters in the 4 slots here.

Lets say that we place a letters on the first slot, b letters on the second, c letters on the third, and d letters on the fourth slot. therefore, a+b+c+d = n.

The first slot is free to place slot -> we have 26^a ways to put it.

The second slot, third slot, fourth slots have a restriction; you cannot place the letter that is at the left of the slot. (you can't place o in the second, third slot, you can't place f in the fourth slot) -> by this restriction, we can prevent duplicates being counted. -> ex) ooaoaaof -> this will be only counted one time. -> therefore, there's 25^(b+c+d) = 26^(n-a) ways to put in the slots.

if a is 0, b+c+d = n. the ways to distribute numbers to b, c, d is H(3,n)=C(3+n-1, n).

if a is 1, b+c+d = n-1. the ways to distribute numbers to b, c, d is H(3,n-1)=C(3+n-1-1, n-1)

...

if a is n, b+c+d = 0 the ways to distribute numbers to b, c, d is H(3,0)=C(3+0-1, 0).

-- therefore the total = sigma k=0 to n (26^k * 25^n-k * H(len(S),n-k))

there was my logic, and I coded it but it came with a result of only 70 out of 100.

Can someone help me finding the counterexample?

Code below:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>

#define ff first
#define ss second
#define MOD 1000000007LL

using namespace std;
using pii = pair<int, int>;
using ll = long long;

vector<ll> f(3000000);

tuple<ll, ll, ll> exgcd(ll a, ll b) {
    if (b == 0)
        return make_tuple(a, 1, 0);
    ll g, x, y;
    tie(g, x, y) = exgcd(b, a % b);
    return make_tuple(g, y, x - (a / b) * y);
}

ll moddiv(ll a, ll b)
{
    ll bb;
    tie(ignore, bb, ignore) = exgcd(b, MOD);
    if (bb < 0) b += MOD;
    return (a * bb) % MOD;
}

ll getC(int a, int b)
{
    if (a < b) return 0;
    return moddiv(moddiv(f[a], f[a - b]), f[b]);
}

ll getH(int a, int b)
{
    return getC(a + b - 1, b);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    f[0] = 1;
    for (int i = 1; i < f.size(); i++) f[i] = (f[i - 1] * i) % MOD;

    int k;
    cin >> k;
    string s;
    cin >> s;
    ll answer = 0;
    vector<ll> p26(k + 1), p25(k + 1);
    p26[0] = p25[0] = 1;
    for (int i = 1; i <= k; i++) {
        p26[i] = (p26[i - 1] * 26) % MOD;
        p25[i] = (p25[i - 1] * 25) % MOD;
    }
    for (int i = 0; i <= k; i++) {
        ll tmp = (p26[i] * getH(s.length(), k - i)) % MOD;
        tmp = (tmp * p25[k - i]) % MOD;
        answer = (answer + tmp) % MOD;
    }
    cout << answer;

    return 0;
}