1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio>10 #include <bitset>11 #include <vector>12 #include <deque>13 #include <queue>14 #include <stack>15 #include <ctime>16 #include <set>17 #include <map>18 #include <cmath>19 using namespace std;20 #define fr first21 #define sc second22 #define cl clear23 #define BUG puts("here!!!")24 #define W(a) while(a--)25 #define pb(a) push_back(a)26 #define Rint(a) scanf("%d", &a)27 #define Rll(a) scanf("%I64d", &a)28 #define Rs(a) scanf("%s", a)29 #define Cin(a) cin >> a30 #define FRead() freopen("in", "r", stdin)31 #define FWrite() freopen("out", "w", stdout)32 #define Rep(i, len) for(int i = 0; i < (len); i++)33 #define For(i, a, len) for(int i = (a); i < (len); i++)34 #define Cls(a) memset((a), 0, sizeof(a))35 #define Clr(a, x) memset((a), (x), sizeof(a))36 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))37 #define lrt rt << 138 #define rrt rt << 1 | 139 #define pi 3.1415926535940 #define RT return41 #define lowbit(x) x & (-x)42 #define onecnt(x) __builtin_popcount(x)43 typedef long long LL;44 typedef long double LD;45 typedef unsigned long long ULL;46 typedef pair<int, int> pii;47 typedef pair<string, int> psi;48 typedef pair<int, int> pll;49 typedef map<string, int> msi;50 typedef vector<int> vi;51 typedef vector<int> vl;52 typedef vector<vl> vvl;53 typedef vector<bool> vb;54 55 const LL mod = 29;56 LL n;57 58 LL mul(LL x, LL q) {59     LL ret = 1;60     while(q) {61         if(q & 1) ret = (ret * x) % mod;62         q >>= 1;63         x = (x * x) % mod;64     }65     return ret;66 }67 68 LL exgcd(LL a, LL b, LL &x, LL &y) {69     if(b == 0) {70         x = 1;71         y = 0;72         return a;73     }74     else {75         LL ret = exgcd(b, a%b, x, y);76         LL tmp = x;77         x = y;78         y = tmp - a / b * y;79         return ret;80     }81 }82 83 LL iv(LL a) {84     LL x, y;85     exgcd(a, mod, x, y);86     return (x % mod + mod) % mod;87 }88 89 signed main() {90     // FRead();91     while(cin >> n && n) {92         cout << ((mul(2, 2*n+1)-1)%mod)*((mul(3, n+1)-1)*iv(2)%mod)*((mul(167,n+1)-1)*iv(166)%mod)%mod << endl;93     }94     RT 0;95 }