using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Numerics;

namespace Problem51Nod

{

    class Program

    {

        public static void Main(String[] args)

        {

            //BigInteger m = BigInteger.Pow(5, 143) - 1;

            //BigInteger n = BigInteger.Pow(2, 331) + 1;

            //int k = 100;

            BigInteger m = BigInteger.Parse(Console.ReadLine());

            BigInteger n = BigInteger.Parse(Console.ReadLine());

            int k = Convert.ToInt32(Console.ReadLine());

            //Stopwatch timer = new Stopwatch();

            //timer.Start();

            Console.WriteLine(Cmn(m, n, k));

            //timer.Stop();

            //Console.WriteLine(timer.Elapsed);

        }

        static BigInteger[][] PowerTable = new BigInteger[][];

        static List<BigInteger[][]>[] PreTable = new List<BigInteger[][]>[];

        static BigInteger[,] CMatrix;

        static void InitCMatrix(int l)

        {

            CMatrix = new BigInteger[l + , l + ];

            for (int i = ; i <= l; i++)

                CMatrix[i, ] = CMatrix[i, i] = ;

            for (int i = ; i <= l; i++)

                for (int j = ; j *  <= i; j++)

                    CMatrix[i, j] = CMatrix[i, i - j] = CMatrix[i - , j - ] + CMatrix[i - , j];

        }

        static void InitPowerTab(int l, int p)

        {

            PowerTable[p] = new BigInteger[l + ];

            PowerTable[p][] = ;

            for (int j = ; j < PowerTable[p].Length; j++)

                PowerTable[p][j] = PowerTable[p][j - ] * p;

        }

        static void InitData(int l, BigInteger max, int p)

        {

            PreTable[p] = new List<BigInteger[][]>();

            BigInteger[] pre = MulTo(l, p);

            BigInteger[,] cMatrix = new BigInteger[l + , l + ];

            for (int i = ; i <= l; i++)

                for (int j = ; j <= i; j++)

                    cMatrix[i, j] = CMatrix[i, j];

            int power = ;

            for (BigInteger i = p; i <= max; i *= p)

            {

                BigInteger[][] cTable = new BigInteger[p - ][];

                cTable[] = pre;

                for (int j = ; j < p; j++)

                {

                    BigInteger[] next = ReplaceWith(cTable[], i * j % PowerTable[p][l], l, p, cMatrix);

                    if (j < p - )

                        cTable[j] = MulMod(cTable[j - ], next, l, p);

                    else

                        pre = MulMod(cTable[j - ], next, l, p);

                }

                PreTable[p].Add(cTable);

                power++;

            }

        }

        static BigInteger Cmn(BigInteger m, BigInteger n, int l)

        {

            InitCMatrix(l);

            InitPowerTab(l, );

            InitPowerTab(l, );

            BigInteger up5 = CalP(m, n, , l);

            BigInteger up2 = CalP(m, n, , l);

            BigInteger mod = ((up5 - up2) + PowerTable[][l]) % PowerTable[][l];

            mod = IMod(PowerTable[][l], mod, PowerTable[][l]) * PowerTable[][l] + up2;

            return mod;

        }

        static BigInteger CalP(BigInteger m, BigInteger n, int p, int l)

        {

            BigInteger count = Count(m, p) - Count(n, p) - Count(m - n, p);

            if (count > l) return ;

            InitData(l, m, p);

            BigInteger up = Cal(m, p, l) * PowerTable[p][(int)count];

            BigInteger down = Cal(n, p, l);

            down *= Cal(m - n, p, l);

            down %= PowerTable[p][l];

            up = IMod(down, up, PowerTable[p][l]);

            return up;

        }

        static BigInteger Count(BigInteger v, BigInteger mod)

        {

            BigInteger count = ;

            while (v > )

            {

                v /= mod;

                count += v;

            }

            return count;

        }

        static List<BigInteger> Values = new List<BigInteger>();

        static List<int> Mods = new List<int>();

        static BigInteger Cal(BigInteger nums, int p, int l)

        {

            BigInteger numsBak = nums;

            Values.Clear();

            Mods.Clear();

            while (numsBak > )

            {

                Values.Add(numsBak);

                Mods.Add((int)(numsBak % p));

                numsBak /= p;

            }

            BigInteger result = ;

            for (int i = ; i < Values.Count; i++)

            {

                result *= CalSingle(i, p, l);

                result %= PowerTable[p][l];

            }

            return result;

        }

        static BigInteger CalSingle(int cIndex, int p, int l)

        {

            int len = Mods[cIndex];

            BigInteger sum = , last = (Values[cIndex] - len) % PowerTable[p][l];

            BigInteger[] pre = new BigInteger[] {  };

            BigInteger result = ;

            cIndex++;

            for (int i = Mods.Count - ; i >= cIndex; i--)

            {

                int index = Mods[i];

                if (index > )

                {

                    BigInteger modValue = , current = ;

                    foreach (var item in PreTable[p][i - cIndex][index - ])

                    {

                        if (item != )

                            current = (current + modValue * item) % PowerTable[p][l];

                        if (sum ==  || modValue == )

                            break;

                        modValue = modValue * sum % PowerTable[p][l];

                    }

                    if (i - cIndex +  <= l)

                        sum = (sum + index * PowerTable[p][i - cIndex + ]) % PowerTable[p][l];

                    result = (result * current) % PowerTable[p][l];

                }

            }

            for (int i = ; i <= len; i++)

            {

                if (i % p == )

                    continue;

                result *= last + i;

                result %= PowerTable[p][l];

            }

            return result;

        }

        static BigInteger[] MulTo(int l, int p)

        {

            BigInteger[] result = new BigInteger[] {  };

            for (BigInteger i = ; i < p; i++)

            {

                if (i % p == )

                    continue;

                BigInteger[] b = new BigInteger[] { i,  };

                result = MulMod(result, b, l, p);

            }

            return result;

        }

        static BigInteger[] MulMod(BigInteger[] a, BigInteger[] b, int l, int p)

        {

            int len = Math.Min(l + , a.Length + b.Length - );

            BigInteger[] result = new BigInteger[len];

            for (int i = ; i < Math.Min(a.Length, l + ); i++)

            {

                if (a[i] == )

                    continue;

                int upper = Math.Min(b.Length, l - i + );

                for (int j = ; j < upper; j++)

                    result[i + j] += a[i] * b[j];

            }

            int last = ;

            for (int i = ; i < result.Length; i++)

            {

                result[i] %= PowerTable[p][l - i];

                if (result[i] > )

                    last = i + ;

            }

            if (last < result.Length)

                Array.Resize(ref result, last);

            return result;

        }

        //2次方算法，考虑大数是3次方 除以大进制的常数

        static BigInteger[] ReplaceWith(BigInteger[] source, BigInteger into, int l, int p, BigInteger[,] cMatrix)

        {

            int len = source.Length;

            len = Math.Min(len, l + );

            BigInteger[] result = new BigInteger[len];

            BigInteger[] power = new BigInteger[len];

            power[] = ;

            for (int i = ; i < len; i++)

                power[i] = power[i - ] * into % PowerTable[p][l];

            for (int i = ; i < len; i++)

            {

                if (source[i] == )

                    continue;

                for (int j = ; j <= i; j++)

                {

                    if (power[i] == ) continue;

                    var tmp = power[i - j] * source[i] % PowerTable[p][l - j];

                    if (tmp == ) continue;

                    result[j] += tmp * cMatrix[i, j];

                }

            }

            for (int i = ; i < result.Length; i++)

                result[i] %= PowerTable[p][l - i];

            return result;

        }

        public static BigInteger EuclidExtend(BigInteger X, BigInteger Y, out BigInteger A, out BigInteger B)

        {

            if (Y == ) { A = ; B = ; return X; }

            BigInteger quotient = X / Y;

            BigInteger gcd = EuclidExtend(Y, X - Y * quotient, out A, out B);

            BigInteger Temp = A; A = B; B = Temp - quotient * A;

            return gcd;

        }

        public static bool Linear(BigInteger X, BigInteger Y, BigInteger N, out BigInteger xResult, out BigInteger yResult)

        {

            BigInteger gcd = EuclidExtend(X, Y, out xResult, out yResult);

            if (N % gcd != ) { return false; }

            xResult = xResult * N / gcd % Y;

            xResult = xResult >=  ? xResult : xResult + Y;

            yResult = yResult * N / gcd % X;

            yResult = yResult <=  ? yResult : yResult - X;

            return true;

        }

        public static BigInteger IMod(BigInteger A, BigInteger B, BigInteger P)

        {

            BigInteger x, y;

            Linear(A, P, B, out x, out y);

            return x;

        }

    }

}