type
    TEdge = record
        start, terminal: longint;
        weight: int64;
    end;
    TEdgeArr = array of TEdge;

operator <(e1, e2: TEdge)res: boolean;
begin
    res := e1.weight < e2.weight;
end;

operator >(e1, e2: TEdge)res: Boolean;
begin
    res := e1.weight > e2.weight;
end;

procedure SortEdge(A: TEdgeArr; l, r: longint);
var
    i, j: longint;
    t, m: TEdge;
begin
    i := l; j := r; m := A[(i+j) >> 1];
    repeat
        while A[i]<m do inc(i);
        while A[j]>m do dec(j);
        if i<=j then
        begin
            t := A[i];
            A[i] := A[j];
            A[j] := t;
            inc(i); dec(j);
        end;
    until i>j;
    if i<r then SortEdge(A, i, r);
    if l<j then SortEdge(A, l, j);
end;

const
    INF: int64 = 1<<60 div 3;
var
    map: array [1..100, 1..100] of int64;
    n, i, j: longint;

{
    @param x: 起始搜索节点
    算法思想：用一个数组维护从各个未加入顶点到
    树的最短边长度，操作n次，每次将距离最短的
    边加入到树中，并更新与之相邻的点的距离值。
}

function prim(x: longint): int64;
{
    lowest: 储存各个节点到树的最短距离
    visited: 标记是否已加入树中
}
var
    lowest: array [1..100] of int64;
    visited: array [1..100] of boolean;
    min: int64;
    i, j, minindex: longint;
begin
    fillchar(visited, sizeof(visited), 0);
    visited[x] := true;

    //先将初始节点加入树中，更新lowest
    for i := 1 to n do
        lowest[i] := map[i, x];

    prim := 0;
    for i := 2 to n do
    begin
        min := INF;

        //找出树到外部节点最短的一条边
        //并将该边加入树中
        for j := 1 to n do
            if (not visited[j]) and (min > lowest[j]) then
            begin
                min := lowest[j];
                minindex := j;
            end;
        visited[minindex] := true;
        prim := prim + min;

        //对新加入的那个节点，
        //更新与其相邻的未加入树的节点的lowest值
        for j := 1 to n do
        begin
            if visited[j] then continue;
            if map[j, minindex] < lowest[j] then
                lowest[j] := map[j, minindex];
        end;
    end;
end;

{
    算法思想：
    1\. 先将边按照长度排序。
    2\. 遍历所有的边，若该边的两个顶点都在树中则跳过；
    否则将其加入树中。
}

function Kruscal: int64;
var
    Edges: TEdgeArr;
    //并查集，储存自己的父亲，若自己为根结点则为自己
    //这是一种常用的写法：否则如果存成0的话，想把两棵
    //树并在一起需要多一步判断。
    UnionSet: array [0..100] of longint;
    i: longint;

    procedure InitEdges; //将邻接矩阵转化为边数组。
    var
        i, j: longint;
        E: TEdge;
    begin
        for i := 1 to n do
            for j := 1 to i-1 do
            begin
                E.start := i;
                E.terminal := j;
                E.weight := map[i, j];
                SetLength(Edges, Length(Edges)+1);
                Edges[High(Edges)] := E;
            end;
        SortEdge(Edges, Low(Edges), High(Edges));
    end;

    //寻找自己的根节点，并把自己直接连到根结点上。
    function Find(x: longint): longint;
    var
        root: longint;
    begin
        root := x;
        while root <> UnionSet[root] do
            root := UnionSet[root];
        UnionSet[x] := root;
        exit(root);
    end;

    //尝试将边的两个顶点并在一个并查集中，如果两个
    //顶点都在同一个集合中则返回False，否则执行合
    //并操作。
    function Union(x, y: longint): boolean;
    var
        px, py: longint;
    begin
        px := Find(x);
        py := Find(y);
        if px = py then
            exit(False);
        UnionSet[px] := py;
        exit(True);
    end;

begin
    Kruscal := 0;
    fillchar(UnionSet, sizeof(UnionSet), 0);
    InitEdges;
    for i := 1 to n do
        UnionSet[i] := i;
    for i := Low(Edges) to High(Edges) do
        if Union(Edges[i].start, Edges[i].terminal) then
        begin
            Kruscal := Kruscal + Edges[i].weight;
        end;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do
        for j := 1 to n do
            read(map[i, j]);
    writeln(Kruscal);

    close(input); close(output);
end.

procedure nx(l, r: longint);
var
    mid, i, j, k: longint;
begin
    if l = r then
    begin
        tmp[l] := a[l];
        exit;
    end;
    mid := (l + r) shr 1;
    nx(l, mid);
    nx(mid+1, r);
    i := l;
    j := mid+1;
    k := l;
    while k <= r do
    begin
        if (j>r) or (i<=mid) and (a[i]<=a[j]) then //注意这里为等号
        begin
            tmp[k] := a[i];
            inc(i);
        end
        else
        begin
            cnt := cnt + mid - i + 1; //加上逆序数
            tmp[k] := a[j];
            inc(j);
        end;
        inc(k);
    end;
    for i := l to r do
        a[i] := tmp[i];
end;

//AC
const
    MODN = 99999997;
type
    rec = record value, index: longint; end;
    TArr = array [1..100000] of rec;
var
    n: longint;
    a, b, c, tmp: TArr;
    ok: Boolean;
    l, r, i, j: longint;
    cnt: int64;

procedure sort(var arr: TArr; l, r: longint);
var
    i, j: longint;
    m, t: rec;
begin
    i := l;
    j := r;
    m := arr[(i+j) shr 1];
    repeat
        while arr[i].value < m.value do inc(i);
        while arr[j].value > m.value do dec(j);
        if i <= j then
        begin
            t := arr[i];
            arr[i] := arr[j];
            arr[j] := t;
            inc(i);
            dec(j);
        end;
    until i >j;
    if i < r then sort(arr, i, r);
    if l < j then sort(arr, l, j);
end;

procedure nx(l, r: longint);
var
    mid, i, j, k: longint;
begin
    if l = r then
    begin
        tmp[l] := c[l];
        exit;
    end;
    mid := (l + r) shr 1;
    nx(l, mid);
    nx(mid+1, r);
    i := l;
    j := mid+1;
    k := l;
    while k <= r do
    begin
        if (j>r) or (i<=mid) and (c[i].index<=c[j].index) then
        begin
            tmp[k] := c[i];
            inc(i);
        end
        else
        begin
            cnt := cnt + mid - i + 1;
            cnt := cnt mod MODN;
            tmp[k] := c[j];
            inc(j);
        end;
        inc(k);
    end;
    for i := l to r do
        c[i] := tmp[i];
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(n);
    for i := 1 to n do
    begin
        read(a[i].value);
        a[i].index := i;
    end;
    for i := 1 to n do
    begin
        read(b[i].value);
        b[i].index := i;
    end;
    sort(a, 1, n);
    sort(b, 1, n);

    for i := 1 to n do
        c[a[i].index] := b[i];

    cnt := 0;
    nx(1, n);
    writeln(cnt);

    close(input); close(output);
end.

const
    modn = 10007;
var
    a, b, k, m, n: longint;
    map: array[0..1000,0..1000] of int64; //缓存
//快速幂
function power(a, x: longint): int64;
var
    t: longint;
begin
    if x = 1 then
        exit(a);
    if x = 0 then
        exit(1);
    t := power(a, x shr 1);
    power := t * t mod modn;
    if odd(x) then
        power := power * a mod modn;
end;
//快速组合数
function C(n, k: longint): int64;
begin
    if map[n, k] > 0 then
        exit(map[n, k]);
    if (n <= k) or (k = 0) then
        C := 1
    else if k = 1 then
        C := n
    else
        C := (C(n-1, k)+C(n-1, k-1)) mod modn;
    map[n, k] := C;
end;

var
    t: longint;
    ans: int64;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(a, b, k, n, m);
    a := a mod modn;
    b := b mod modn;
    ans := power(a, n);
    ans := ans * power(b, m) mod modn;
    //C(k,n)与C(k,m)是等效的，计算较小者即可
    if n > m then n := m;
    ans := ans * C(k, n) mod modn;
    writeln(ans);

    close(input); close(output);
end.

const
    JINDU = 100000;
var
    n: Integer;
//在数字前补0
procedure PrintANumber(x: longint);
var
    t: longint;
begin
    if x = 0 then
        write('00000')
    else
    begin
        t := JINDU;
        while t > x * 10 do
        begin
            write(0);
            t := t div 10;
        end;
        write(x);
    end;
end;

var
    ans: array [1..300] of longint;
    len, i: integer;
//计算2^(n-1)
procedure calc2;
var
    i, x, t, mul: longint;
begin
    len := 1;
    ans[1] := 1;
    t := n-1;
    while t > 0 do
    begin
        if t < 6 then
            mul := 1 << t
        else
            mul := 64;
        x := 0;
        for i := 1 to len do
        begin
            ans[i] := ans[i] * mul + x;
            x := ans[i] div JINDU;
            ans[i] := ans[i] mod JINDU;
        end;
        if x > 0 then
        begin
            inc(len);
            ans[len] := x;
        end;
        dec(t, 6);
    end;
end;
//除以3
procedure div3;
var
    i, x, t: longint;
begin
    i := len;
    x := 0;
    while i > 0 do
    begin
        t := (x * JINDU + ans[i]);
        ans[i] := t div 3;
        x := t mod 3;
        dec(i);
    end;
    while ans[len] = 0 do dec(len);
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    while not eof do
    begin
        readln(n);
        if n=1 then   //特殊情况处理
        begin
            writeln(0);
            continue;
        end;
        fillchar(ans, sizeof(ans), 0);
        calc2;
        if odd(n) then
            dec(ans[1])
        else
            inc(ans[1]);
        div3;
        write(ans[len]);
        for i := len-1 downto 1 do
            PrintANumber(ans[i]);
        writeln;
    end;

    close(input); close(output);
end.

var
    n, _, i: longint;

function h: int64; inline;
var
    k, t: longint;
begin
    h := 0;
    t := trunc(sqrt(n));
    k := 1;
    while k <=t do
    begin
        h := h + n div k;
        inc(k);
    end;
    h := h * 2 - t * t;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(n);
        if n <= 0 then
            writeln(0)
        else
            writeln(h);
    end;

    close(input);
    close(output);
end.

const
    operators: array [1..4] of char = ('*', '+', '-', #0); //符号
var
    s: string;
    _, n: integer;
    op: array [0..10] of char;
    yes: Boolean;

function toValue(ch: char): integer;
begin
    exit(ord(ch) - ord('0'));
end;

procedure calcAndPrint;
var
    numtop, opstop: Integer;  //数字栈，符号栈
    num: array [1..10] of longint;
    ops: array [1..10] of char;
    i: integer;
begin
    i := 1;
    numtop := 1;
    num[numtop] := toValue(s[1]);
    opstop := 0;
    while i <= n do
    begin
        while (i < n) and (op[i] = #0) do
        begin
            inc(i);
            num[numtop] := num[numtop] * 10 + toValue(s[i]);
        end;
        if (op[i] in ['+', '-']) or (i >= n) then
        begin
            while (opstop > 0) and (ops[opstop] = '*') do
            begin
                dec(opstop);
                num[numtop - 1] := num[numtop] * num[numtop -1];
                dec(numtop);
            end;
        end;
        if i >= n then break;
        inc(opstop);
        ops[opstop] := op[i];
        inc(i);
        inc(numtop);
        num[numtop] := toValue(s[i]);
    end;
    i := 1;
    while i < numtop do
    begin
        if ops[i] = '+' then
            num[i+1] := num[i] + num[i+1]
        else
            num[i+1] := num[i] - num[i+1];
        inc(i);
    end;
    if (num[numtop] = 2000) and (opstop > 0) then
    begin
        yes := True;
        write('  ');
        for i := 1 to n do
        begin
            write(s[i]);
            if op[i] <> #0  then
                write(op[i]);
        end;
        writeln('=');
    end;
end;

procedure dfs(t: integer); //搜索第t个位置
var
    i: Integer;
    ch: char;
begin
    if t = n then
    begin
        calcAndPrint;
        exit;
    end;
    for i := 1 to 4 do
    begin
        ch := operators[i];
        if (ch = #0) and (s[t] = '0') and ((t = 1) or (t > 1) and (op[t-1] <> #0)) then continue;
        op[t] := ch;
        dfs(t+1);
    end;
end;

var
    i: Integer;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(s);
    _ := 0;
    while not eof and (s[1] <> '=') do
    begin
        i := 1;
        while not (s[i] in ['0'..'9', '=']) do
        begin
            inc(i);
        end;
        delete(s, 1, i-1);
        n := pos('=', s) - 1;
        inc(_);
        writeln('Problem ', _);
        yes := False;
        fillchar(op, sizeof(op), 0);
        dfs(1);
        if not yes then
            writeln('  IMPOSSIBLE');
        readln(s);
    end;

    close(input); close(output);
end.

//Accepted.
const
    dx: array [1..4] of integer = (1, 0, 0, -1);
    dy: array [1..4] of integer = (0, 1, -1, 0);
    dir: array [1..4] of char = ('e', 'n', 's', 'w');

var
    a: array [1..50, 1..2] of integer; //障碍物
    k, i, n, _, x, y: integer;
    ans: array [1..20] of char;
    tot: longint;
    vis: array [-220..220, -220..220] of boolean;

function judge(x1, y1, x2, y2: longint): Boolean; //判断刚刚走过的路上是否有障碍物
var
    i: Integer;
begin
    judge := False;
    if x1 = x2 then
    begin
        for i := 1 to k do
            if (a[i, 1] = x1) and ((a[i, 2] - y1)*(a[i, 2] - y2) <= 0) then exit;
    end
    else
        for i := 1 to k do
            if (a[i, 2] = y2) and ((a[i, 1] - x1)*(a[i, 1] - x2) <= 0) then exit;
    judge := True;
end;

procedure print;
var
    i: Integer;
begin
    for i := 1 to n do write(ans[i]);
    writeln;
    inc(tot);
end;

procedure dfs(t, x, y, d, s: integer);
var
    i, sum: Integer;
    tx, ty: longint;
begin
    if t = n then
    begin
        if (x = 0) and (y = 0) then print;
        exit;
    end;

    sum := s - t - 1;
    inc(t);

    for i := 1 to 4 do
    begin
        if (i = d) or (i + d = 5) then continue;   //方向相同或相反
        tx := x + dx[i] * t;
        ty := y + dy[i] * t;
        if vis[tx, ty] then continue;              //走过
        if abs(tx) + abs(ty) > sum then continue;  //回不去，剪枝
        if not judge(x, y, tx, ty) then continue;  //有障碍物
        ans[t] := dir[i];
        vis[tx, ty] := True;
        dfs(t, tx, ty, i, sum);
        vis[tx, ty] := False;
    end;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);

    readln(_);
    while _ > 0 do
    begin
        dec(_);
        read(n, k);
        fillchar(vis, sizeof(vis), 0);
        for i := 1 to k do
            read(a[i, 1], a[i, 2]);
        fillchar(ans, sizeof(ans), 0);
        tot := 0;
        dfs(0, 0, 0, -1, n * (n+1) div 2);
        writeln('Found ', tot, ' golygon(s).');
        writeln;
    end;

    close(input); close(output);
end.

const
  maxn = 20000;
type
  NodeRec = record
    Value: string;
    l, r, index: longint;
  end;
  Node = record
      left, right: longint;   //Index of left and right child in the `tree` array, -1 for none.
      Rec: NodeRec;
      index: longint;
  end;
  //以下为哈希表的定义
  _PNode = ^_Node;
  _Node = record
    n: Node;
    next: _PNode;
  end;

  HashTable = object
    arr: array [0..maxn] of _PNode;
    function hash(n: NodeRec): longint;
    procedure add(n: Node);
    procedure clear;
    function find(n: NodeRec): longint;
  end;

procedure HashTable.clear;
var
  i: longint;
  p, q: _PNode;
begin
  for i := 0 to maxn do
  begin
    p := arr[i];
    while p<>nil do
    begin
      q := p^.next;
      dispose(p);
      p := q;
    end;
  end;
  fillchar(arr, sizeof(arr),0);
end;

function cmp(r1, r2: NodeRec): Boolean;
begin
  cmp := (r1.l = r2.l) and (r1.r = r2.r) and (r1.Value = r2.Value);
end;

function HashTable.hash(n: NodeRec): longint;
var
  i: longint;
begin
  hash := 0;
  for i := 1 to length(n.Value) do
    hash := (hash*5 + ord(n.Value[i]) - ord('a')) mod maxn;
  hash := (hash + n.l * 10 + n.r * 5) mod maxn;
end;

procedure HashTable.add(n: Node);
var
  h: longint;
  p, q: _PNode;
begin
  h := hash(n.rec);
  new(q);
  fillchar(q^, sizeof(_Node), 0);
  q^.next := arr[h];
  q^.n := n;
  arr[h] := q;
end;

function HashTable.find(n: NodeRec): longint;
var
  p: _PNode;
begin
  find := -1;
  p := arr[hash(n)];
  while (p<>nil) and not cmp(n, p^.n.rec) do p := p^.next;
  if p <> nil then
    find := p^.n.index;
end;
//哈系表定义结束
var
  inputs: Ansistring;
  _: longint;
  tree: array [1..50001] of Node;
  cur: longint;              //The current pointer of the input string.
  num: longint;              //The current number of the `tree` array.
  ls: longint;
  t: longint;
  tot: longint;
  ht: HashTable;

function build: longint; //建树
label lb;
var
  rec: NodeRec;
  i,j,l,r: longint;
begin
  l := 0;
  r := 0;
  fillchar(rec, sizeof(rec), 0);
  inc(tot);
  rec.index := tot;
  while (cur<=ls) and (inputs[cur] in ['a'..'z']) do
  begin
    rec.Value := rec.Value+inputs[cur];
    inc(cur);
  end;
  if cur>ls then goto lb;    //。。。这里被迫跳转控制流，由于实在不想多谢，就用了臭名昭著的label
  if inputs[cur] = '(' then
  begin
    inc(cur);
    l := build();
    rec.l := tree[l].rec.index;
    inc(cur);
    r := build();
    rec.r := tree[r].rec.index;
    inc(cur);
  end;
  j := ht.find(rec);
  if j>0 then
  begin
    dec(tot);
    exit(j);
  end
  else
  begin
lb:
    inc(num);
    tree[num].left := l;
    tree[num].right := r;
    tree[num].rec := rec;
    tree[num].index := num;
    ht.add(tree[num]);
    exit(num);
  end;
end;

procedure print(n: longint);
begin
  if tree[n].rec.index > t then
  begin
    write(tree[n].rec.Value);
    t := tree[n].rec.index;
  end
  else
  begin
    write(tree[n].rec.index);
    exit;
  end;
  if tree[n].right = 0 then
    exit;
  write('(');
  print(tree[n].left);
  write(',');
  print(tree[n].right);
  write(')');
end;
begin
  assign(input, 'main.in'); reset(input);
  assign(output, 'main.out'); rewrite(output);
  readln(_);
  fillchar(ht.arr, sizeof(ht.arr),0);
  while _>0 do
  begin
    dec(_);
    readln(inputs);
    fillchar(tree, sizeof(tree), 0);
    ht.clear;
    ls := length(inputs);
    cur := 1;  num := 0; tot := 0;
    build;
    t := 0;
    print(num);
    writeln;
  end;
  close(input); close(output);
end.

var
    pre, mid, s: string;
    tree: array [1..50] of record
        l, r: integer;
        ch: char;
    end;
    cur: integer;
function init: integer;
var
    m: integer;
begin
    readln(s);
    m := length(s) >> 1 + 1;
    pre := Copy(s, 1, m-1);
    mid := Copy(s, m+1, length(s));
    init := m-1;
end;
function build(l1, l2, r2: integer): integer;
var
    m,len: integer;
    t: integer;
begin
    if l2 > r2 then exit(0); //该子树不存在。**这个地方坑了我很久**
    inc(cur);
    t := cur;      // 这里也坑了我，当下面构造完左右子树后，cur已经变了，所以要缓存起来
    build := t;
    tree[t].ch := pre[l1];
    if r2-l2 = 0 then //叶节点
        exit;
    m := pos(pre[l1], mid); //在中序遍历中找根节点
    len := m - l2;
    tree[t].l := build(l1+1, l2, m-1); //构造左子树
    tree[t].r := build(l1+len+1, m+1, r2); //构造右子树
end;
procedure print(x: integer);
begin
    if x = 0 then exit;
    print(tree[x].l);
    print(tree[x].r);
    write(tree[x].ch);
end;
begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);
    while not eof do
    begin
        fillchar(tree, sizeof(tree), 0);
        cur := 0;
        build(1, 1, init);
        print(1);
        writeln;
    end;
    close(input);
    close(output);
end.

var
    x: qword;
    y: longint;
begin
    x := 1<<64-1;
    y := 100;
    x := x mod y; //报错201
    x := x mod qword(y); //正确
end.

var
    a,b: qword;
    _, n, i, k, cnt: longint;
    f: array [1..1000000] of longint;

function superMod(a, b: qword; m: longint): longint;
var
    x: qword;
begin
    if b = 0 then
        exit(1);
    x := superMod(a, b shr 1, m);
    superMod := x * x mod m;
    if odd(b) then
        superMod := superMod * a mod m;
end;

begin
    assign(input, 'main.in'); reset(input);
    assign(output, 'main.out'); rewrite(output);
    readln(_);
    while _ > 0 do
    begin
        dec(_);
        readln(a, b, n);
        if a = 0 then
        begin
            writeln(0);
            continue;
        end;
        if n = 1 then
        begin
            writeln(0);
            continue;
        end;
        f[1] := 1;
        f[2] := 1;
        cnt := 2;
        while not ((f[cnt-1] = 1) and (f[cnt] = 0)) do
        begin
            inc(cnt);
            f[cnt] := (f[cnt-1] + f[cnt-2]) mod n;
        end;
        //while x > int64(1 <<60) do
        //    x := x - int64((cnt << 59));
        a := a mod qword(cnt);
        k := superMod(a, b, cnt);
        writeln(f[k]);
    end;
    close(output); close(input);
end.