def parse_term(expr):
        rat_expo, sym_expo = Rational(1), None
        sexpr, deriv = expr, None

        if isinstance(expr, Pow):
            if isinstance(expr.base, Derivative):
                sexpr, deriv = parse_derivative(expr.base)
            else:
                sexpr = expr.base

            if isinstance(expr.exp, Rational):
                rat_expo = expr.exp
            elif isinstance(expr.exp, Mul):
                coeff, tail = term.exp.as_coeff_terms()

                if isinstance(coeff, Rational):
                    rat_expo, sym_expo = coeff, Basic.Mul(*tail)
                else:
                    sym_expo = expr.exp
            else:
                sym_expo = expr.exp
        elif isinstance(expr, Basic.exp):
            if isinstance(expr[0], Rational):
                sexpr, rat_expo = Basic.exp(Rational(1)), expr[0]
            elif isinstance(expr[0], Mul):
                coeff, tail = expr[0].as_coeff_terms()

                if isinstance(coeff, Rational):
                    sexpr, rat_expo = Basic.exp(Basic.Mul(*tail)), coeff
        elif isinstance(expr, Derivative):
            sexpr, deriv = parse_derivative(expr)

        return sexpr, rat_expo, sym_expo, deriv

def radsimp(expr):
    """
    Rationalize the denominator.

    Examples:
    =========
        >>> from sympy import *
        >>> radsimp(1/(2+sqrt(2)))
        1 - 1/2*2**(1/2)
        >>> x,y = map(Symbol, 'xy')
        >>> e = ( (2+2*sqrt(2))*x+(2+sqrt(8))*y )/( 2+sqrt(2) )
        >>> radsimp(e)
        x*2**(1/2) + y*2**(1/2)
    """
    n,d = fraction(expr)
    a,b,c = map(Wild, 'abc')
    r = d.match(a+b*Basic.sqrt(c))
    if r is not None:
        a = r[a]
        if r[b] == 0:
            b,c = 0,0
        else:
            b,c = r[b],r[c]

        syms = list(n.atoms(type=Basic.Symbol))
        n = collect( (n*(a-b*Basic.sqrt(c))).expand(), syms )
        d = a**2 - c*b**2

    return n/d

    def _eval_apply(self, z, a=S.One):
        z, a = map(Basic.sympify, (z, a))

        if isinstance(a, Basic.Number):
            if isinstance(a, Basic.NaN):
                return S.NaN
            elif isinstance(a, Basic.Zero):
                return self(z)

        if isinstance(z, Basic.Number):
            if isinstance(z, Basic.NaN):
                return S.NaN
            elif isinstance(z, Basic.Infinity):
                return S.One
            elif isinstance(z, Basic.Zero):
                if a.is_negative:
                    return S.Half - a - 1
                else:
                    return S.Half - a
            elif isinstance(z, Basic.One):
                return S.ComplexInfinity
            elif isinstance(z, Basic.Integer):
                if isinstance(a, Basic.Integer):
                    if z.is_negative:
                        zeta = (-1)**z * Basic.bernoulli(-z+1)/(-z+1)
                    elif z.is_even:
                        B, F = Basic.bernoulli(z), Basic.Factorial(z)
                        zeta = 2**(z-1) * abs(B) * pi**z / F

                    if a.is_negative:
                        return zeta + Basic.harmonic(abs(a), z)
                    else:
                        return zeta - Basic.harmonic(a-1, z)

    def _eval_apply(cls, arg):
        arg = Basic.sympify(arg)

        if isinstance(arg, Basic.Number):
            if isinstance(arg, Basic.NaN):
                return S.NaN
            elif isinstance(arg, Basic.Infinity):
                return S.Infinity
            elif isinstance(arg, Basic.Integer):
                if arg.is_positive:
                    return Basic.Factorial(arg-1)
                else:
                    return S.ComplexInfinity
            elif isinstance(arg, Basic.Rational):
                if arg.q == 2:
                    n = abs(arg.p) / arg.q

                    if arg.is_positive:
                        k, coeff = n, S.One
                    else:
                        n = k = n + 1

                        if n & 1 == 0:
                            coeff = S.One
                        else:
                            coeff = S.NegativeOne

                    for i in range(3, 2*k, 2):
                        coeff *= i

                    if arg.is_positive:
                        return coeff*Basic.sqrt(S.Pi) / 2**n
                    else:
                        return 2**n*Basic.sqrt(S.Pi) / coeff

    def __new__(cls, f, z, **assumptions):
        f = Basic.sympify(f)

        if not f.is_polynomial(z):
            return f

        obj = Basic.__new__(cls, **assumptions)
        obj._args = (f.as_polynomial(z), z)

        return obj

def separate(expr, deep=False):
    """Rewrite or separate a power of product to a product of powers
       but without any expanding, ie. rewriting products to summations.

       >>> from sympy import *
       >>> x, y, z = symbols('x', 'y', 'z')

       >>> separate((x*y)**2)
       x**2*y**2

       >>> separate((x*(y*z)**3)**2)
       x**2*y**6*z**6

       >>> separate((x*sin(x))**y + (x*cos(x))**y)
       x**y*cos(x)**y + x**y*sin(x)**y

       #>>> separate((exp(x)*exp(y))**x)
       #exp(x*y)*exp(x**2)

       Notice that summations are left un touched. If this is not the
       requested behaviour, apply 'expand' to input expression before:

       >>> separate(((x+y)*z)**2)
       z**2*(x + y)**2

       >>> separate((x*y)**(1+z))
       x**(1 + z)*y**(1 + z)

    """
    expr = Basic.sympify(expr)

    if isinstance(expr, Basic.Pow):
        terms, expo = [], separate(expr.exp, deep)
        #print expr, terms, expo, expr.base

        if isinstance(expr.base, Mul):
            t = [ separate(Basic.Pow(t,expo), deep) for t in expr.base ]
            return Basic.Mul(*t)
        elif isinstance(expr.base, Basic.exp):
            if deep == True:
                return Basic.exp(separate(expr.base[0], deep)*expo)
            else:
                return Basic.exp(expr.base[0]*expo)
        else:
            return Basic.Pow(separate(expr.base, deep), expo)
    elif isinstance(expr, (Basic.Add, Basic.Mul)):
        return type(expr)(*[ separate(t, deep) for t in expr ])
    elif isinstance(expr, Basic.Function) and deep:
        return expr.func(*[ separate(t) for t in expr])
    else:
        return expr

 def __new__(cls, arg, expr):
     if not isinstance(arg, Argument):
         raise TypeError("arg must be of type `Argument`")
     expr = _sympify(expr)
     if not isinstance(expr, (Expr, MatrixExpr)):
         raise TypeError("Unsupported expression type %s." % type(expr))
     return Basic.__new__(cls, arg, expr)

    def __new__(cls, *components):
        if components and not isinstance(components[0], Morphism):
            # Maybe the user has explicitly supplied a list of
            # morphisms.
            return CompositeMorphism.__new__(cls, *components[0])

        normalised_components = Tuple()

        for current, following in zip(components, components[1:]):
            if not isinstance(current, Morphism) or \
                    not isinstance(following, Morphism):
                raise TypeError("All components must be morphisms.")

            if current.codomain != following.domain:
                raise ValueError("Uncomposable morphisms.")

            normalised_components = CompositeMorphism._add_morphism(
                normalised_components, current)

        # We haven't added the last morphism to the list of normalised
        # components.  Add it now.
        normalised_components = CompositeMorphism._add_morphism(
            normalised_components, components[-1])

        if not normalised_components:
            # If ``normalised_components`` is empty, only identities
            # were supplied.  Since they all were composable, they are
            # all the same identities.
            return components[0]
        elif len(normalised_components) == 1:
            # No sense to construct a whole CompositeMorphism.
            return normalised_components[0]

        return Basic.__new__(cls, normalised_components)

    def __new__(cls, *args):
        from sympy.matrices.immutable import ImmutableDenseMatrix
        args = map(sympify, args)
        mat = ImmutableDenseMatrix(*args)

        obj = Basic.__new__(cls, mat)
        return obj

    def __new__(cls, subset, superset):
        """
        Default constructor.

        It takes the subset and its superset as its parameters.

        Examples:
        >>> from sympy.combinatorics.subsets import Subset
        >>> a = Subset(['c','d'], ['a','b','c','d'])
        >>> a.subset
        ['c', 'd']
        >>> a.superset
        ['a', 'b', 'c', 'd']
        >>> a.size
        2
        """
        if len(subset) > len(superset):
            raise ValueError("Invalid arguments have been provided. The superset must be larger than the subset.")
        for elem in subset:
            if elem not in superset:
                raise ValueError("The superset provided is invalid as it does not contain the element %i" % elem)
        obj = Basic.__new__(cls)
        obj._subset = subset
        obj._superset = superset
        return obj

    def __new__(cls, *args, **kw_args):
        """
        Constructor for the Permutation object.

        Examples
        ========

        >>> from sympy.combinatorics.permutations import Permutation
        >>> p = Permutation([0,1,2])
        >>> p
        Permutation([0, 1, 2])
        >>> q = Permutation([[0,1],[2]])
        >>> q
        Permutation([[0, 1], [2]])
        """
        if not args or not is_sequence(args[0]) or len(args) > 1 or \
           len(set(is_sequence(a) for a in args[0])) > 1:
            raise ValueError('Permutation argument must be a list of ints or a list of lists.')

        # 0, 1, ..., n-1 should all be present

        temp = [int(i) for i in flatten(args[0])]
        if set(range(len(temp))) != set(temp):
            raise ValueError("Integers 0 through %s must be present." % len(temp))

        cform = aform = None
        if args[0] and is_sequence(args[0][0]):
            cform = [list(a) for a in args[0]]
        else:
            aform = list(args[0])

        ret_obj = Basic.__new__(cls, (cform or aform), **kw_args)
        ret_obj._cyclic_form, ret_obj._array_form = cform, aform
        return ret_obj

 def __new__(cls, func, center=[0,0,0], direction=[0,0,1], **kwargs):
     center = Mat(center)
     direction = Mat(direction)
     if norm(direction) == 0:
         raise ValueError
     direction = normalize(direction)
     return Basic.__new__(cls, func, center, direction)

    def __new__(cls, *args, **kwargs):
        check = kwargs.get('check', True)

        obj = Basic.__new__(cls, *args)
        if check:
            validate(*args)
        return obj

 def __new__(cls, mat):
     mat = _sympify(mat)
     if not mat.is_Matrix:
         raise TypeError("mat should be a matrix")
     if not mat.is_square:
         raise ShapeError("Inverse of non-square matrix %s" % mat)
     return Basic.__new__(cls, mat)

 def __new__(cls, e, z, z0, dir="+"):
     e = sympify(e)
     z = sympify(z)
     z0 = sympify(z0)
     obj = Basic.__new__(cls)
     obj._args = (e, z, z0, dir)
     return obj

    def __new__(cls, *args, **options):
        # (Try to) sympify args first
        newargs = []
        for ec in args:
            pair = ExprCondPair(*ec)
            cond = pair.cond
            if cond == false:
                continue
            if not isinstance(cond, (bool, Relational, Boolean)):
                raise TypeError(
                    "Cond %s is of type %s, but must be a Relational,"
                    " Boolean, or a built-in bool." % (cond, type(cond)))
            newargs.append(pair)
            if cond == True:
                break

        if options.pop('evaluate', True):
            r = cls.eval(*newargs)
        else:
            r = None

        if r is None:
            return Basic.__new__(cls, *newargs, **options)
        else:
            return r

    def __new__(cls, *args, **kw_args):
        """
        The constructor for the Prufer object.

        Examples
        ========
        >>> from sympy.combinatorics.prufer import Prufer

        A Prufer object can be constructed from a list of node connections
        and the number of nodes:

        >>> a = Prufer([[0, 1], [0, 2], [0, 3]], 4)
        >>> a.prufer_repr
        [0, 0]

        A Prufer object can be constructed from a Prufer sequence:

        >>> b = Prufer([1, 3])
        >>> b.tree_repr
        [[2, 1], [1, 3], [3, 0]]
        """
        ret_obj = Basic.__new__(cls, *args, **kw_args)
        if isinstance(args[0][0], list):
            ret_obj._tree_repr = args[0]
            ret_obj._nodes = args[1]
        else:
            ret_obj._prufer_repr = args[0]
            ret_obj._nodes = len(ret_obj._prufer_repr) + 2
        return ret_obj

    def __new__(cls, partition, integer=None):
        """
        Generates a new IntegerPartition object from a list or dictionary.

        The partition can be given as a list of positive integers or a
        dictionary of (integer, multiplicity) items. If the partition is
        preceeded by an integer an error will be raised if the partition
        does not sum to that given integer.

        Examples
        ========

        >>> from sympy.combinatorics.partitions import IntegerPartition
        >>> a = IntegerPartition([5, 4, 3, 1, 1])
        >>> a
        IntegerPartition(14, (5, 4, 3, 1, 1))
        >>> print a
        [5, 4, 3, 1, 1]
        >>> IntegerPartition({1:3, 2:1})
        IntegerPartition(5, (2, 1, 1, 1))

        If the value that the partion should sum to is given first, a check
        will be made to see n error will be raised if there is a discrepancy:
        >>> IntegerPartition(10, [5, 4, 3, 1])
        Traceback (most recent call last):
        ...
        ValueError: The partition is not valid

        """
        from sympy.ntheory.residue_ntheory import int_tested

        if integer is not None:
            integer, partition = partition, integer
        if isinstance(partition, (dict, Dict)):
            _ = []
            for k, v in sorted(partition.items(), reverse=True):
                if not v:
                    continue
                k, v = int_tested(k, v)
                _.extend([k]*v)
            partition = tuple(_)
        else:
            partition = tuple(sorted(int_tested(partition), reverse=True))
        sum_ok = False
        if integer is None:
            integer = sum(partition)
            sum_ok = True
        else:
            integer = int_tested(integer)

        if not sum_ok and sum(partition) != integer:
            raise ValueError("Partition did not add to %s" % integer)
        if any(i < 1 for i in partition):
            raise ValueError("The summands must all be positive.")

        obj = Basic.__new__(cls, integer, partition)
        obj.partition = list(partition)
        obj.integer = integer
        return obj

 def _new(cls, *args, **kwargs):
     if len(args) == 1 and isinstance(args[0], ImmutableMatrix):
         return args[0]
     rows, cols, flat_list = cls._handle_creation_inputs(*args, **kwargs)
     rows = Integer(rows)
     cols = Integer(cols)
     mat = Tuple(*flat_list)
     return Basic.__new__(cls, rows, cols, mat)

    def __new__(cls, *args, **kwargs):
        args = list(map(sympify, args))
        check = kwargs.get('check', True)

        obj = Basic.__new__(cls, *args)
        if check:
            validate(*args)
        return obj