What happens to the value of $$$d(a_1, a_2, a_3)$$$ if you perform an operation on $$$a_1$$$ and $$$a_3$$$?

What happens if you perform an operation on $$$a_1$$$ and $$$a_2$$$?

Can we use negative values to improve the worst answer?

#include <bits/stdc++.h>
using namespace std;
 
int32_t main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        int a, b, c; cin >> a >> b >> c;
        cout << ((a + c - 2 * b) % 3 == 0 ? 0 : 1) << "\n"; 
    }        
    return 0;
}

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        println(Math.min(readLine()!!.split(" ").map { it.toInt() }.sum() % 3, 1))
    }
}

t=int(input())
for i in range(t):
    a,b,c=[int(x) for x in input().split()]
    print(0 if ((a+b+c)%3 == 0) else 1)

What can you say about the number of $0$s and $1$s that are in positions where they should not be in the final string?

What is the minimum number of operations required to sort the string given this relationship between the number of such $0$s and $1$s?

#include <bits/stdc++.h>
using namespace std;
 
int32_t main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        int n; cin >> n;
        string s; cin >> s;
        if(is_sorted(s.begin(), s.end()))
        {
            cout << 0 << "\n";
            continue;
        }
        
        string t = s;
        sort(t.begin(), t.end());
        cout << 1 << "\n";
        vector<int> ans;
        for(int i = 0; i < n; i++)
        {
            if(s[i] != t[i])
                ans.push_back(i+1);
        }
        cout << ans.size() << " ";
        for(int i = 0; i < ans.size(); i++)
            cout << ans[i] << " \n"[i+1 == ans.size()];
    }        
    return 0;
}

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val s = readLine()!!
        if("10" in s) {
            println(1);
            val res = s.toCharArray().sorted().withIndex().filter { it.value != s[it.index] }.map { it.index + 1 }
            println("$$${res.size} $$${res.joinToString(" ")}");
        } else {
            println(0);
        }
        
    }
}

q = int(input())
for tc in range(q):
    n = int(input())
    s = input()
    t = ''.join(sorted(s))
    ans = []
    for i in range(len(s)):
        if s[i] != t[i]: 
            ans.append(i)
    val = 1 if len(ans) > 0 else 0
    print(val)
    if val > 0:
        print(len(ans), end = " ")
    for elem in range(len(ans)):
        print(ans[elem] + 1, end = " ")
    print()

Think about small substrings.

What are the strings that satisfy the given conditions?

If you got WA on pretest $$$2$$$, then you're probably not checking $$$7$$$ length strings.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e6 + 5;
 
int n;
string s;
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n >> s;
		int ans = 1e9;
		for(int i = 0; i < n; i++)
		{
			vector<int> f(3, 0);
			f[s[i] - 'a']++;
			for(int j = i + 1; j < min(n, i + 7); j++)
			{
				f[s[j] - 'a']++;
				if(f[0] > f[1] && f[0] > f[2])
					ans = min(ans, j - i + 1);
			}
		}
		if(ans == 1e9)
			ans = -1;
		cout << ans << endl;
	}
	return 0;
}

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val s = readLine()!!
        var ans = 8;
        for(i in 0..n-1) {
            val cnt = IntArray(3) {0}
            for(j in i..Math.min(i + 6, n - 1)) {
                cnt[s[j] - 'a']++;
                if(j > i && cnt[0] > Math.max(cnt[1], cnt[2]))
                    ans = Math.min(ans, j - i + 1);
            }
        }
        if(ans > 7)
            ans = -1;
        println(ans)
    }
}

When is $$$u \oplus v \nleq min(u, v)$$$?

If $$$u \oplus v \nleq min(u, v)$$$ for any $$$u$$$ that is adjacent to $$$v$$$, the player cannot make move and will lose.

Can you relabel the nodes in such a way that $$$u \oplus v \nleq min(u, v)$$$ for any $$$u$$$ and $$$v$$$ which share an edge? Think bipartite.

The number of occurrences of (almost) every 'class' of nodes of the same kind is a unique power of $$$2$$$.

Thinking about the binary representation of a number is often useful in competitive programming.

/**
 * the_hyp0cr1t3
 * 24.09.2021 01:19:28
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif
 
template<class T> class Y {
    T f;
public:
    template<class U> explicit Y(U&& f): f(forward<U>(f)) {}
    template<class... Args> decltype(auto) operator()(Args&&... args) {
        return f(ref(*this), forward<Args>(args)...);
    }
}; template<class T> Y(T) -> Y<T>;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int Q; cin >> Q;
 
    while(Q--) []() {
        int i, j, k, n;
        cin >> n;
        vector<vector<int>> g(n);
        for(i = 0; i < n - 1; i++) {
            int u, v; cin >> u >> v;
            g[--u].push_back(--v); g[v].push_back(u);
        }
 
        int lg = 32 - __builtin_clz(n);
        vector<vector<int>> vals(lg);
        for(i = 1; i <= n; i++)
            vals[31 - __builtin_clz(i)].push_back(i);
 
        vector<int> col(n);
        Y([&](auto dfs, int v, int p) -> void {
            for(auto& x: g[v]) if(x ^ p) {
                col[x] = col[v] ^ 1;
                dfs(x, v);
            }
        })(0, -1);
 
        int w = accumulate(col.begin(), col.end(), 0);
        if(w > n - w) {
            w = n - w;
            for(auto& x: col) x ^= 1;
        }
 
        vector<int> ans(n);
        for(i = j = k = 0; k < lg; k++) {
            for(auto x: vals[k]) {
                if(w >> k & 1) {
                    while(!col[i]) i++;
                    ans[i++] = x;
                } else {
                    while(col[j]) j++;
                    ans[j++] = x;
                }
            }
        }
 
        for(i = 0; i < n; i++)
            cout << ans[i] << " \n"[i + 1 == n];
    }();
 
} // ~W

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
const int N = 2e5 + 5;
 
int n;
int msb[N], ans[N];
vector<int> nodes[2];
vector<int> g[N];
 
void precompute()
{
	int bit = 1, cnt = 1, nxt = 2;
	for(int i = 1; i < N; i++)
	{
		msb[i] = bit;
		cnt--;
		if(cnt == 0)
			cnt = nxt, bit++, nxt *= 2;
	}
}
 
void dfs(int u, int par, int col)
{
	nodes[col].push_back(u);
	for(auto &v: g[u])
	{
		if(v == par)
			continue;
		dfs(v, u, col ^ 1);
	}
}
 
 
int32_t main()
{
	IOS;
	precompute();
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
			g[i].clear();
		for(int i = 1; i <= n - 1; i++)
		{
			int u, v;
			cin >> u >> v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1, 0, 0);
		vector<vector<int> > v(20);
		for(int i = 1; i <= n; i++)
			v[msb[i]].push_back(i);
		for(int i = 19; i >= 0; i--)
		{
			int cur = 0;
			if(nodes[cur ^ 1].size() > nodes[cur].size())
				cur ^= 1;
			for(auto &it:v[i])
			{
				int node = nodes[cur].back();
				nodes[cur].pop_back();
				ans[node] = it;
			}
		}
		for(int i = 1; i <= n; i++)
			cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

fun dfs(x: Int, p: Int, curcol: Int, adj: Array<MutableList<Int>>, col: Array<Int>) {
    col[x] = curcol
    adj[x]
        .filter { it != p }
        .forEach { dfs(it, x, curcol xor 1, adj, col) }
}
 
fun main(args: Array<String>) {
    val t = readLine()!!.toInt()
    repeat(t) {
        val n = readLine()!!.toInt()
        val adj = Array(n) { mutableListOf<Int>() }
        repeat(n - 1) {
            val (u, v) = readLine()!!.split(" ").map { it.toInt() }
            adj[u - 1].add(v - 1);
            adj[v - 1].add(u - 1);
        }
        val col = Array<Int>(n) {0}
        dfs(0, -1, 0, adj, col)
        var s = Array(2) { mutableListOf<Int>() }
        (0..n-1).forEach { s[col[it]].add(it) }
        if(s[0].size < s[1].size)
            s[0] = s[1].also { s[1] = s[0] }
        val highestBit = Array(20) { mutableListOf<Int>() }
        (1..n).forEach { highestBit[it.takeHighestOneBit().countTrailingZeroBits()].add(it - 1) }
        val ans = Array<Int>(n) {-1}
        (19 downTo 0).forEach { currentBit ->
            val largerSet = if(s[0].size >= s[1].size) 0 else 1
            highestBit[currentBit].forEach { it ->
                ans[it] = s[largerSet].last()
                s[largerSet].removeLast()
            }
        }
        val pos = Array<Int>(n) {-1}
        (0..n-1).forEach { pos[ans[it]] = it };
        (0..n-1).forEach { print ("${pos[it] + 1} ") }
        println()
    }
}

How would you solve the problem for one query?

Assume the value of $$$b_1$$$ to be some variable, say $$$x$$$.

Try finding the number of operations applied at each index in terms of $$$x$$$.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const long long INF = 1e18;
 
const int N = 2e5+5; 
 
int n, m, a[N], b[N], c[N], add[N], mob[N];
 
void mobius() 
{
    mob[1] = 1;
    for(int i = 2; i < N; i++)
    {
        mob[i]--;
        for(int j = i + i; j < N; j += i) 
        {
          mob[j] -= mob[i];
        }
    }
}
 
int32_t main()
{
    IOS;
    mobius();
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
        c[i] = b[i] - a[i];
    c[1] = 0;
    vector<int> z;
    for(int i = 1; i <= n; i++)
    {
        int d = c[i];
        for(int j = i; j <= n; j += i)
        {
            c[j] -= d;
        }
        add[i] = d;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(mob[i] == 0)
            ans += abs(add[i]);
        else if(mob[i] == -1)
            z.push_back(-add[i]);
        else 
            z.push_back(add[i]);
    }
    sort(z.begin(), z.end());
    vector<int> pref = z;
    for(int i = 1; i < sz(z); i++)
        pref[i] = pref[i-1] + z[i];
    auto sum = [&pref](int l, int r)
    {
        if(r < 0) return 0LL;
        int res = pref[r];
        if(l-1 >= 0)
            res -= pref[l-1];
        return res;
    };
    int q; cin >> q;
    while(q--)
    {
        int x; cin >> x;
        x -= a[1];
        int lo = 0, hi = sz(z)-1;
        while(lo <= hi)
        {
            int mid = (lo+hi)/2;
            if(z[mid] <= -x)
                lo = mid+1;
            else
                hi = mid-1;
        }
        swap(lo, hi);
        int res = sum(hi, sz(z)-1) + (sz(z)-hi) * x;
        res -= (sum(0, lo) + (lo+1)*x);
        cout << ans+res << endl;
    }
    return 0;
}

How can you check if an array is good?

Is there any relation between a bad array and a good array?

How can we define a unique good subsequence of a bad array?

Can we somehow count the number of bad arrays using this?

Can we modify our choice of subsequence such that we can easily count the number of ways of choosing the remaining elements?

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
 
const int maxn = 105;
 
int t, n, k, MOD, modinv[maxn], fact[maxn], invfact[maxn], cnt_distinct_positive[maxn][maxn], cnt_total[maxn][maxn], cnt_bad[maxn][maxn], pow2[maxn * maxn];
// cnt_distinct_positive[i][j] = ways of choosing i distinct positive values with a combined of exactly j bits on.
// cnt_total[i][j] = total number of arrays of length i with exactly j bits on in total
// cnt_bad[i][j] = number of bad arrays of length i with exactly j bits on in total
 
int mod_expo(int x, int p)
{
    if(!p)
        return 1;
    int res = mod_expo(x, p / 2);
    res *= res;
    res %= MOD;
    if(p & 1)
        res *= x;
    return res % MOD;
}
 
int mod_inv(int x)
{
    return mod_expo(x, MOD - 2);
}
 
// O(1) with O(n) precalc needed
int fast_nCr(int x, int r)
{
    assert(x < maxn && r >= 0 && r <= x);
    int num = fact[x];
    int denom = (invfact[r] * invfact[x - r]) % MOD;
    return (num * denom) % MOD;
}
 
// O(x - r)
int slow_nPr(int x, int r)
{
    assert(r >= 0 && r < maxn);
    int res = 1;
    for(int j = 1; j <= r; j++)
    {
        res *= (x - j + 1 + MOD) % MOD;
        res %= MOD;
    }
    return res;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> MOD;
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < maxn; i++)
    {
        modinv[i] = mod_inv(i);
        fact[i] = (fact[i - 1] * i) % MOD;
        invfact[i] = mod_inv(fact[i]);
    }
    pow2[0] = 1;
    for(int i = 1; i <= n * k; i++)
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            // The number of ways of selecting i distinct positive values with upto j bits set in total
            cnt_distinct_positive[i][j] = slow_nPr((mod_expo(2, j) - 1 + MOD) % MOD, i);
            // The number of ways of selecting i non-negative values with upto j bits set
            cnt_total[i][j] = pow2[i * j];
            // Inclusion exclusion to get the count for exactly j bits for both values.
            for(int l = 0; l < j; l++)
            {
                cnt_distinct_positive[i][j] += (MOD - ((fast_nCr(j, l) * cnt_distinct_positive[i][l])) % MOD);
                cnt_distinct_positive[i][j] %= MOD;
                cnt_total[i][j] += (MOD - ((fast_nCr(j, l) * cnt_total[i][l])) % MOD);
                cnt_total[i][j] %= MOD;
            }
        }
    }
    // An empty array is good.
    cnt_total[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= k; j++)
        {
            cnt_bad[i][j] = 0;
            // i' <=> a, j' <=> b
            for(int a = 0; a < i; a++)
                for(int b = 0; b < j; b++)
                {
                    // The only case where this incorrect addition of "bad" arrays of size $$$i$$$ occurs is when we consider good 
                    // arrays of size $$$i - 1$$$ for odd $$$i$$$ during this process. So while calculating the answer for $$$n$$$ in the 
                    // problem we just have to skip good arrays of size $$$n - 1$$$ if $$$n$$$ is odd. 
                    if(i == n && (n & 1) && a == i - 1)
                        continue;
                    // f(i, j, i', j')
                    int cur_bad = 1;
                    // The number of ways of good arrays of length $$$i'$$$ distinct positive values with exactly $$$j'$$$ bits set in total:
                    cur_bad *= (cnt_total[a][b] - cnt_bad[a][b] + MOD) % MOD;
                    cur_bad %= MOD;
                    // The number of ways of selecting $$$i - i'$$$ distinct positive values with exactly $$$j - j'$$$ bits set in total. 
                    cur_bad *= cnt_distinct_positive[i - a][j - b];
                    cur_bad %= MOD;
                    // The number of ways of distributing the $$$i - i'$$$ values among the existing good array of length $$$i'$$$:
                    cur_bad *= fast_nCr(i, a);
                    cur_bad %= MOD;
                    // The number of ways of choosing which $$$j'$$$ of the $$$j$$$ bits were from the good array.
                    cur_bad *= fast_nCr(j, b);
                    cur_bad %= MOD;
                    // The number of ways of choosing the remaining $$$j'$$$ bits of each of the $$$i - i'$$$ distinct values.
                    cur_bad *= pow2[(i - a) * b];
                    cur_bad %= MOD;
                    cnt_bad[i][j] += cur_bad;
                    cnt_bad[i][j] %= MOD;
                }
        }
    int ans = 0;
    for(int j = 0; j <= k; j++)
    {
        int cnt_good = (cnt_total[n][j] - cnt_bad[n][j] + MOD) % MOD;
        // The number of ways of choosing the j bits from the k total bits.
        ans += (fast_nCr(k, j) * cnt_good) % MOD;
        ans %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
using namespace __gnu_pbds;
using namespace std;
 
using ll = long long;
using ld = long double;
 
typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;
 
#define mp make_pair
 
int MOD;
 
int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}
 
int add(int a, int b) {
    int s = (a+b);
    if (s>=MOD) s-=MOD;
    return s;
}
 
int sub(int a, int b) {
    int s = (a+MOD-b);
    if (s>=MOD) s-=MOD;
    return s;
}
 
int po(int a, ll deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}
 
int inv(int n)
{
    return po(n, MOD-2);
}
 
 
mt19937 rnd(time(0));
 
 
const int LIM = 40000;
 
vector<int> facs(LIM), invfacs(LIM);
 
vector<vector<int>> C(400, vector<int>(400));
vector<int> degs(LIM);
 
void init()
{
    facs[0] = 1;
    for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
    invfacs[LIM-1] = inv(facs[LIM-1]);
    for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
 
    for (int i = 0; i<400; i++)
    for (int j = 0; j<=i; j++)
    {
        C[i][j] = mul(facs[i], mul(invfacs[j], invfacs[i-j]));
    }
    degs[0] = 1;
    for (int i = 1; i<LIM; i++) degs[i] = mul(2, degs[i-1]);
}
 
 
 
int solve1(int n, int k)
{
    vector<vector<int>> ch_diff(n+1, vector<int>(k+1));
 
    //Choose len distinct nonzero numbers from 1 to 2^k-1 such that each bit is present somewhere
 
    for (int len = 1; len<=n; len++)
    {
        for (int bits = 1; bits<=k; bits++)
        {
            int tot = sub(degs[bits], 1);
            ch_diff[len][bits] = 1;
            for (int i = 0; i<len; i++) {
                ch_diff[len][bits] = mul(ch_diff[len][bits], sub(tot, i));
            }
            //ch[len][bits] = mul(ch[len][bits], invfacs[len]);
 
            for (int bits1 = 1; bits1<bits; bits1++)
            {
                ch_diff[len][bits] = sub(ch_diff[len][bits], mul(ch_diff[len][bits1], C[bits][bits1]));
            }
        }
    }
 
    ch_diff[0][0] = 1;
 
    /*cout<<"CH_DIFF:"<<endl;
 
    for (int len = 0; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<ch_diff[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
 
    vector<vector<int>> ch(n+1, vector<int>(k+1));
 
    //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere
 
    for (int len = 0; len<=n; len++)
    {
        for (int bits = 0; bits<=k; bits++)
        {
            ch[len][bits] = degs[bits*len];
 
            for (int bits1 = 0; bits1<bits; bits1++)
            {
                ch[len][bits] = sub(ch[len][bits], mul(ch[len][bits1], C[bits][bits1]));
            }
        }
    }
 
    /*cout<<"CH:"<<endl;
 
    for (int len = 1; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<ch[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
    vector<vector<int>> dp_part(n+1, vector<int>(k+1));
 
    //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere and it's impossible to permutate
 
    for (int len = 1; len<=n; len++)
    {
        for (int bits = 0; bits<=k; bits++)
        {
            int ans = 0;
            for (int sz_bad = 1; sz_bad<=len; sz_bad++)
                for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
                {
                    int good_rem = sub(ch[len-sz_bad][bits-bits_bad], dp_part[len-sz_bad][bits-bits_bad]);
                    //good arrays of length len-sz_bad on exactly bits-bits_bad bits
                    int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
 
                    adding = mul(adding, C[len][sz_bad]);
                    adding = mul(adding, C[bits][bits_bad]);
                    adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
                    ans = add(ans, adding);
                }
            dp_part[len][bits] = ans;
        }
    }
 
    /*cout<<"DP_PART:"<<endl;
 
    for (int len = 1; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<dp_part[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
    int answer = 0;
 
    int min_sz_bad = 1; if (n%2==1) min_sz_bad = 2;
 
    for (int bits = 0; bits<=k; bits++)
    {
        int subans = 0;
        for (int sz_bad = min_sz_bad; sz_bad<=n; sz_bad++)
            for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
            {
                int good_rem = sub(ch[n-sz_bad][bits-bits_bad], dp_part[n-sz_bad][bits-bits_bad]);
                //good arrays of length len-sz_bad on exactly bits-bits_bad bits
                int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
 
                adding = mul(adding, C[n][sz_bad]);
                adding = mul(adding, C[bits][bits_bad]);
                adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
                subans = add(subans, adding);
                //cout<<bits<<' '<<sz_bad<<' '<<bits_bad<<": "<<subans<<endl;
            }
        subans = sub(ch[n][bits], subans);
        subans = mul(subans, C[k][bits]);
        //cout<<ch[n][bits]<<' '<<subans<<endl;
        answer = add(answer, subans);
 
    }
    return answer;
}
 
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int n, k; cin>>n>>k>>MOD;
    init();
    cout<<solve1(n, k)<<endl;
 
}

fun mod_expo(base: Int, pow: Int, MOD: Int): Long {
    if(pow == 0) {
        return 1;
    }
    var res = mod_expo(base, pow / 2, MOD)
    res = (res * res) % MOD
    if(pow % 2 == 1) {
        res = (res * base) % MOD;
    }
    return res;
}
 
fun mod_inv(base: Int, MOD: Int): Long {
    return mod_expo(base, MOD - 2, MOD)
}
 
fun fast_nCr(n: Int, r: Int, fact: Array<Long>, invfact: Array<Long>, MOD: Int): Long {
    val num = fact[n];
    val denom = (invfact[r] * invfact[n - r]) % MOD;
    return (num * denom) % MOD;
}
 
fun slow_nPr(n: Int, r: Int, MOD: Int): Long {
    var res = 1L;
    for(i in 1..r) {
        res *= (n - i + 1 + MOD) % MOD;
        res %= MOD;
    }
    return res;
}
 
fun main(args: Array<String>) {
    val (n, k, MOD) = readLine()!!.split(" ").map { it.toInt() }
    val fact = Array<Long>(Math.max(n, k) + 1) { 1L }
    val invfact = Array<Long>(Math.max(n, k) + 1) { 1L }
    for(i in 1..Math.max(n, k)) {
        fact[i] = (fact[i - 1] * i) % MOD
        invfact[i] = mod_inv(fact[i].toInt(), MOD)
    }
    val pow2 = Array<Long>(n * k + 1) { 1 }
    for(i in 1..n*k) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }
    val cntDistinctPositive = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    val cntTotal = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    val cntBad = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    for(i in 0..n) {
        for(j in 0..k) {
            cntDistinctPositive[i][j] = slow_nPr((mod_expo(2, j, MOD).toInt() - 1 + MOD) % MOD, i, MOD)
            cntTotal[i][j] = pow2[i * j]
            for(l in 0..j-1) {
                cntDistinctPositive[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntDistinctPositive[i][l])) % MOD)
                cntDistinctPositive[i][j] = cntDistinctPositive[i][j] % MOD
                cntTotal[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntTotal[i][l])) % MOD);
                cntTotal[i][j] = cntTotal[i][j] % MOD
            }
        }
    }
    cntTotal[0][0] = 1
    for(i in 1..n) {
        for(j in 0..k) {
            cntBad[i][j] = 0
             for(a in 0..i-1) {
                for(b in 0..j-1) {
                    if(i == n && n % 2 == 1 && a == i - 1) {
                        continue;
                    }
                    var curBad = (cntTotal[a][b] - cntBad[a][b] + MOD) % MOD
                    curBad *= (cntDistinctPositive[i - a][j - b])
                    curBad = curBad % MOD
                    curBad *= fast_nCr(i, a, fact, invfact, MOD)
                    curBad = curBad % MOD
                    curBad *= fast_nCr(j, b, fact, invfact, MOD)
                    curBad = curBad % MOD
                    curBad *= pow2[(i - a) * b]
                    curBad = curBad % MOD
                    cntBad[i][j] += curBad
                    cntBad[i][j] = cntBad[i][j] % MOD
                }
            }
        }
    }
    var ans = 0L
    for(j in 0..k) {
        val cntGood = (cntTotal[n][j] - cntBad[n][j] + MOD) % MOD
        ans += (fast_nCr(k, j, fact, invfact, MOD) * cntGood) % MOD
    }
    println(ans % MOD)
}