Pagini recente » Cod sursa (job #1866746) | Cod sursa (job #1641846) | Cod sursa (job #1873) | Cod sursa (job #562056) | Cod sursa (job #2466932)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("functii.in");
ofstream g("functii.out");
const int mod = 30103, maxn = 1e4+5;
int n, s;
int pwr(int x, int y) {
if(y == 0) { return 1; }
if(y == 1) { return x; }
int half = pwr(x, y / 2);
if(y % 2 == 0) {
return (half * half) % mod;
} else {
return (half * half * x) % mod;
}
}
struct xy { int x, y; };
int fact[maxn];
xy ee(int a, int b) {
if(b == 0) {
return {1, 0};
}
xy ls = ee(b, a % b);
return {ls.y, ls.x - (a / b) * ls.y};
}
int im(int x) {
int r = ee(x, mod).x;
r = (r + mod) % mod;
return r;
}
int comb(int n, int k) {
return (((fact[n] * im(fact[k])) % mod) * im(fact[n - k])) % mod;
}
int query(int n, int k) {
return comb(n, k);
}
int main()
{
f >> n >> s;
fact[0] = 1;
for(int i = 1; i <= n; i ++) {
fact[i] = fact[i-1] * i;
fact[i] %= mod;
}
int ans = pwr(2, s) - 2;
ans *= query(n, n - s);
ans %= mod;
g << ans << '\n';
f.close(); g.close();
return 0;
}