## Editorial for CALCULATE POW(2004,X) MOD 29

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const ar:array[2..4] of integer=(2,3,167);
var n,re,t,i,j,s:longint;
m:array[2..4] of longint;
a:array[2..4,1..100] of longint;
procedure init;
var i,j:byte;
begin
a[2,1]:=2; a[3,1]:=3; a[4,1]:=22;
for i:=2 to 4 do
begin
m[i]:=2;
a[i,2]:=(a[i,1]*ar[i]) mod 29;
end;
for i:=2 to 4 do
begin
while a[i,m[i]]<>a[i,1] do
begin
inc(m[i]);
a[i,m[i]]:=(a[i,m[i]-1]*ar[i]) mod 29;
end;
dec(m[i]);
end;
end;

begin
init;
repeat
if n=0 then break;
t:=(2*n+1) mod m[2];
if t=0 then t:=m[2];
re:=(a[2,t]+28) mod 29;
for i:=3 to 4 do
begin
t:=(n+1) mod m[i];
if t=0 then t:=m[i];
dec(t);
s:=1;
for j:=1 to t do s:=(s+a[i,j]) mod 29;
re:=(re*s) mod 29;
end;
writeln(re);
until false;
end.


#### Code mẫu của happyboy99x

#include<cstdio>

#define MOD 29

int powmod(int a, int n) {
if(n == 0) return 1;
int res = powmod(a, n/2);
return n % 2 ? res * res * a % MOD : res * res % MOD;
}

int main() {
int x;
while(scanf("%d",&x) != EOF && x != 0) {
printf("%d\n", (powmod(2,x+x+1)-1)*(powmod(3,x+1)-1)*powmod(2,MOD-2)*(powmod(167,x+1)-1)*powmod(166,MOD-2) % MOD);
}
return 0;
}


#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

using namespace std;

int powMod(int a, int p) {
if (p == 1) return a % 29;
int x = powMod(a, p >> 1);
x = x * x % 29;
if (p & 1) return x * a % 29;
return x;
}

int cnt[2004];

int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("MMOD29.in", "r", stdin);
int power;
while (cin >> power) {
if (power == 0) break;
int x = 2004;
RESET(cnt, 0);
for (int i = 2; i <= x; ++i)
while (x % i == 0) {
cnt[i] += power;
x /= i;
}
int ans = 1;
FOR(i, 2, 2004)
if (cnt[i]) {
ans = ans * (powMod(i, cnt[i] + 1) + 28) * powMod(i - 1, 27) % 29;
}
cout << ans << endl;
}
return 0;
}


#### Code mẫu của RR

{$R+,Q+} {$inline on}
uses math;
var
x             :       longint;

function get(a,n:longint):longint;
var
k,p,t:longint;
begin
if n=0 then exit(0);
if n=1 then exit(1);
k:=n>>1;
p:=get(a,k);
t:=(p*p*(a-1)+p<<1) mod 29;
if n and 1=0 then exit(t);
exit(((a*t)+1) mod 29);
end;

begin
while (x>0) do
begin
writeln((get(2,2*x+1)*get(3,x+1)*get(167,x+1)) mod 29);
end;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
long f(long a,long n)
{
if(n==1)
return a;
else if(n%2!=0)
return a*f(a,n-1)%29;
else
{
double y=pow(f(a,n/2),2);
long x=long(y);
if(y-x>0.1)
return (x+1)%29;
else return x%29;
}
}
main()
{
long x[30],n,a,b,c,KQ;
for(long i=0;i<=28;i++)
x[i]=(21*i)%29;
while(scanf("%ld",&n)&&n>0)
{
a=f(2,2*n+1)-1;
for(long i=0;i<=28;i++)
if(f(22,n+1)-1==x[i])
b=i;
if(f(3,n+1)%2!=0)
c=(f(3,n+1)-1)/2;
else c=(f(3,n+1)+28)/2;
//printf("%ld %ld %ld %ld ",a,b,c,f(22,n+1));
KQ=a*b*c%29;
printf("%ld\n",KQ);
}
//getch();
}


#### Code mẫu của ll931110

#include <cstdio>
#include <iostream>
#define VAL 29
using namespace std;

int calc(int x, int p)
{
int i,t;

x = x % VAL;
p = p % (VAL - 1);

if (p == 0) return 0;
else
{
t = 1;
for (i = 0; i < p; i++)
t = (t * x) % VAL;

t--;
while (t % (x - 1) != 0)
{
t += VAL;
}

i = t / (x - 1);
return i;
}
}

int main()
{
int v,n;

do
{
cin >> n;
if (n != 0)
{
v = calc(2, 2 * n + 1);
v = (v * calc(3, n + 1)) % VAL;
v = (v * calc(167, n + 1)) % VAL;
cout << v << endl;
}
}
while (n != 0);
return 0;
}


#### Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE} {$mode delphi}

function pow(x,n : integer) : integer;
var
t : integer;
begin
if n=0 then pow := 1
else
begin
t := pow(x,n div 2);
if n mod 2 = 0 then pow := t * t mod 29
else pow := t * t * x mod 29;
end;
end;

var
r, x : integer;

begin
while true do
begin
if x=0 then break;
r := 1;
r := r * (28 + pow(3,x+1)) * pow(2, 27) mod 29;
r := r * (28 + pow(167,x+1)) * pow( 166, 27) mod 29;
r := r * (28 + pow(2,2*x+1)) mod 29;
writeln(r);
end;
end.