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)-1,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

include

include

include

include

include

include

include

include

include

include

include

include

include

include

include

define ff first

define ss second

define MOD 1000000007LL

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

vector 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;

}

`