equal := proc(x::list, xoffset::nonnegint, y::list, yoffset::nonnegint)
  local i, k;
  k := nops(x);
  for i from 1 to k do
    if x[i+xoffset mod k+1] <> y[i+yoffset mod k+1] then
      break;
    end if;
  end do;
  return evalb(i=k+1);
end;
calcperiod := proc(x::list, a::list, m::posint)
  local k, i, j, X, Y, Z, n, period, preperiod;
  k := nops(x);
  X := x mod m;
  Y := X;
  Z := X;

  for i from 0 do
    if equal(X, i mod k, Y, 2*i mod k) and i>0 then
      n := i;
      period := i;
      break;
    end if;
    X[i mod k+1] := X[i mod k+1]*a[k] + a[k+1] mod m;
    Y[2*i mod k+1] := Y[2*i mod k+1]*a[k] + a[k+1] mod m;
    for j from 1 to k-1 do
      X[i mod k+1] := X[i mod k+1] + X[i+j mod k+1]*a[k-j] mod m;
      Y[2*i mod k+1] := Y[2*i mod k+1] + Y[2*i+j mod k+1]*a[k-j] mod m;
    end do;
    Y[2*i+1 mod k+1] := Y[2*i+1 mod k+1]*a[k] + a[k+1] mod m;
    for j from 1 to k-1 do
      Y[2*i+1 mod k+1] := Y[2*i+1 mod k+1] + Y[2*i+1+j mod k+1]*a[k-j] mod m;
    end do;
  end do;

  for i from 0 do
    if equal(X, n+i mod k, Z, i mod k) then
      preperiod := i;
      break;
    end if;
    X[n+i mod k+1] := X[n+i mod k+1]*a[k] + a[k+1] mod m;
    Z[i mod k+1] := Z[i mod k+1]*a[k] + a[k+1] mod m;
    for j from 1 to k-1 do
      X[n+i mod k+1] := X[n+i mod k+1] + X[n+i+j mod k+1]*a[k-j] mod m;
      Z[i mod k+1] := Z[i mod k+1] + Z[i+j mod k+1]*a[k-j] mod m;
    end do;
    if equal(X, i mod k, Y, n+i mod k) and period=n then
      period := i+1;
    end if;
  end do;
  return period, preperiod;
end;