#include <stdio.h>
#include <stdlib.h>

typedef  unsigned long long  u8;

//
// Dice allows a user program to call dice->choose(n) to make choices, but the user program will be called
// for all legal combinations of choices.  It's a poor man's prolog.
// The user needs to avoid calling choose(0).
//
class Dice
{
    static const u8 sc_u8bits = 64; // bits per u8
    static const u8 sc_size = 1024; // number of u8's in state
    static const u8 sc_bits = sc_u8bits * sc_size; // total number of bits
    
    u8 m_state[sc_size]; // the actual dice bits
    u8 m_offset; // the lowest used dice bit

    
    Init()
    {
        // initialize the state to zero
        for (u8 i=0; i<sc_size; ++i)
        {
            m_state[i] = 0;
        }
    }
    

    // Set bits sc_bits-offset-logn to sc_bits-offset-1
    void Mask(u8 logn)
    {
        u8 index = m_offset / sc_u8bits;
        u8 shift = m_offset % sc_u8bits;
        u8 mask = (((u8)1)<<logn)-1;
        m_state[index] |= (mask << shift);
        if (sc_u8bits-shift < logn)
        {
            m_state[index+1] |= (mask >> (sc_u8bits-shift));
        }
    }
    
    
    // read bits sc_bits-offset-logn to sc_bits-offset-1
    u8 Read(u8 logn)
    {
        u8 index = m_offset / sc_u8bits;
        u8 shift = m_offset % sc_u8bits;
        u8 mask = (((u8)1)<<logn)-1;
        u8 result = (m_state[index] & (mask << shift)) >> shift;
        if (sc_u8bits-shift < logn)
        {
            result |= (m_state[index+1] & (mask >> (sc_u8bits-shift))) << (sc_u8bits-shift);
        }
        return result;
    }
    
    
    // Increment the state at sc_bits-offset-1.  Return TRUE if we can't.
    bool Inc()
    {
        u8 index = m_offset / sc_u8bits;
        u8 shift = m_offset % sc_u8bits;
        m_state[index] += (((u8)1)<<shift);
        while (m_state[index] == 0 && ++index < sc_size)
        {
            m_state[index] += 1;
        }
        return (index == sc_size);
    }
    
    
public:

    // choose a value in 0..n-1
    u8 Choose(u8 n)
    {
        u8 logn;
        u8 result;
        
        // check that the dice aren't too big
        if (n > 0x8000000000000000L) {
            fprintf(stderr, "Error: Can't do choose(%ull), %ull is too big\n", n, n);
            exit(1);
        }
        
        // figure out how many bits to use
        for (logn=0; (((u8)1)<<logn) < n; ++logn) ;

        if (m_offset < logn)
        {
            fprintf(stderr, "Error: Too many dice rolls\n");
            exit(1);
        }
        
        // use this many bits
        m_offset -= logn;

        // read the result
        result = Read(logn);
        
        if (result >= n-1) 
        {
            // If we've reached n-1, pretend we've reached (1<<logn)-1
            if (result == n-1)
            {
                Mask(logn);
            }
            else
            {
                result = n-1;
            }
        }
        
        return result;
    }

    
    void Exec(void (*callback)(Dice *d, void *context), void *context)
    {
        // call user callback with all possible sets of choices
        for (;;)
        {
            // call the user's callback with a new set of choices
            m_offset = sc_bits;
            (*callback)(this, context);
            
            // increment the state; quit when we wrap around
            if (Inc())
            {
                break;
            }
        }
    }

    
    Dice()
    {
        Init();
    }

    
    ~Dice()
    {
    }
};


static int count_solutions = 0;

// So, there's sc_nGuys on an island, and one weighs a little more or less than the others.
// And there's no scales, but there's a seesaw.
// Can you tell which guy is the odd weight by using the seesaw no more than 3 times?
class Island
{
    static const int sc_nGuys = 14;
    static const int sc_nChoices = 13;  // 1 first choice, 3 second choices, 9 third choices
    static const int sc_nBuckets = 4;  // 0 = unknown, 1 = not light, 2 = not heavy, 3 = equal

    int m_guys[sc_nGuys];  
    int m_count[sc_nBuckets];  // count of each state
    int m_choice[sc_nChoices][2*sc_nBuckets];

    Island()
    {
        for (int i = 0;  i < sc_nChoices;  i++)
            for (int  j = 0;  j < 2*sc_nBuckets;  j++)
                m_choice[i][j] = -1;
    }
    
    void Init()
    {
        for (int i = 0;  i < sc_nGuys;  i++)
            m_guys[i] = 0;
        m_count[0] = sc_nGuys;
        m_count[1] = 0;
        m_count[2] = 0;
        m_count[3] = 0;
    }

    void ChooseFromBucket(Dice* d, int choice, int iBucket, bool isLeft, int* me, int them, int remaining)
    {
        int maxVal = *me;
        int minVal = 0;
        int thisBucket = m_count[iBucket];
        if (isLeft)
        {
            if (maxVal > thisBucket)
                maxVal = thisBucket;
            if (remaining < *me)
                minVal = *me - remaining;
        }
        else
        {
            thisBucket -= m_choice[choice][iBucket];
            if (maxVal > thisBucket)
                maxVal = thisBucket;
            if (remaining < *me + them)
                minVal = *me + them - remaining;
        }
        
        int val = minVal;
        if (maxVal > minVal)
        {
            val = minVal + d->Choose(maxVal + 1 - minVal);
        }
        else if (maxVal < minVal)
        {
            printf("choice %d %d  %d %d %d\n", iBucket, isLeft, *me, m_count[iBucket], val);
            printf("error! %d %d %d max < min: %d < %d\n", choice, iBucket, thisBucket, maxVal, minVal);
            Show();
        }

        
        if (val > thisBucket)
        {
            printf("error! x %d %d  %d %d %d\n", iBucket, isLeft, val, m_count[iBucket], thisBucket);
            Show();
        }

        m_choice[choice][iBucket + (isLeft ? 0 : sc_nBuckets)] = val;
        *me -= val;
    }
    
    // return -1 (left is heavier), 0 (both are equal), or 1 (right is heavier)
    int OneMeasure(Dice* d, int oddGuy, bool heavier, int choice, bool* fail)
    {
        int leftGuys[sc_nGuys];
        int rightGuys[sc_nGuys];
        int nLeft;
        int nRight;
        int i;
        int rsl;

        // Decide what to measure
        if (m_choice[choice][0] == -1)
        {
            int limit = sc_nGuys/2;
            if (limit > sc_nGuys - m_count[3])
                limit = sc_nGuys - m_count[3];

            // Choose number of guys on the left.
            nLeft = 1 + d->Choose(limit);

            // Choose number of guys on the right.
            // If you put the guys at equal distances from the center you need nLeft==nRight.
            // But if you're careful about where you place them you can compare n guys against m guys.

            // nRight = nLeft;
            nRight = 1 + d->Choose(nLeft);

            if (nRight > nLeft)
            {
                printf("error! nRight > nLeft, %d > %d\n", nRight, nLeft);
            }

            // Choose which buckets to draw the guys from
            int remaining = sc_nGuys;
            bool different = (nLeft != nRight);
            for (int b = 0;  b < sc_nBuckets;  b++)
            {
                remaining -= m_count[b];
                ChooseFromBucket(d, choice, b, true, &nLeft, nRight, remaining);
                ChooseFromBucket(d, choice, b, false, &nRight, nLeft, remaining);

                // avoid redundant choices where the left is bigger than the right
                if (!different && m_choice[choice][b] != m_choice[choice][b + sc_nBuckets])
                {
                    different = true;
                    if (m_choice[choice][b] > m_choice[choice][b + sc_nBuckets])
                    {
                        *fail = true;
                        return false;
                    } 
                }
            }

            // adding guys known to be equal on both sides can always be simplified by not adding them
            if (m_choice[choice][3] > 0 && m_choice[choice][3 + sc_nBuckets] > 0)
            {
                *fail = true;
                return false;
            }
        }

        // Do the measurement.  Fill in the left and right guys and figure out which has the odd guy.
        nLeft = 0;
        nRight = 0;
        rsl = 0;
        for (int b = 0;  b < sc_nBuckets;  b++)
        {
            i = 0;
            for (int j = 0;  j < m_choice[choice][b]; i++)
            {
                if (m_guys[i] == b)
                {
                    ++j;
                    leftGuys[nLeft++] = i;
                    if (i == oddGuy)
                        rsl = heavier ? -1 : 1;
                }
            }
            for (int j = 0;  j < m_choice[choice][b + sc_nBuckets]; i++)
            {
                if (m_guys[i] == b)
                {
                    ++j;
                    rightGuys[nRight++] = i;
                    if (i == oddGuy)
                        rsl = heavier ? 1 : -1;
                }
            }
        }

        // Now we know the measurement, so we can change classifications of all the guys
        if (rsl == 0)
        {
            // everyone on the left and the right are equal weight
            for (int i = 0;  i < nLeft;  i++)
            {
                m_count[3]++;
                if (--m_count[m_guys[leftGuys[i]]] < 0)
                    printf("%d a error neg count %d %d\n", rsl, leftGuys[i], m_guys[leftGuys[i]]);
                m_guys[leftGuys[i]] = 3;
            }
            for (int i = 0;  i < nRight;  i++)
            {
                m_count[3]++;
                if (--m_count[m_guys[rightGuys[i]]] < 0)
                    printf("%d b error neg count %d %d\n", rsl, rightGuys[i], m_guys[rightGuys[i]]);
                m_guys[rightGuys[i]] = 3;
            }
        }
        else
        {
            // left guys are heavier and right are lighter (or vice versa)
            for (int i = 0;  i < nLeft;  i++)
            {
                int newValue = m_guys[leftGuys[i]] | (rsl == -1 ? 1 : 2);
                m_count[newValue]++;
                if (--m_count[m_guys[leftGuys[i]]] < 0)
                    printf("%d c error neg count %d %d\n", rsl, leftGuys[i], m_guys[leftGuys[i]]);
                m_guys[leftGuys[i]] = newValue + sc_nBuckets;
            }
            for (int i = 0;  i < nRight;  i++)
            {
                int newValue = m_guys[rightGuys[i]] | (rsl == -1 ? 2 : 1);
                m_count[newValue]++;
                if (--m_count[m_guys[rightGuys[i]]] < 0)
                    printf("%d d error neg count %d %d\n", rsl, rightGuys[i], m_guys[rightGuys[i]]);
                m_guys[rightGuys[i]] = newValue + sc_nBuckets;
            }

            // unmeasured guys are all equal
            for (int i = 0;  i < sc_nGuys;  i++)
            {
                if (m_guys[i] & sc_nBuckets)
                    m_guys[i] -= sc_nBuckets;
                else
                {
                    if (--m_count[m_guys[i]] < 0)
                        printf("%d e error neg count %d %d\n", rsl, i, m_guys[i]);
                    m_count[3]++;
                    m_guys[i] = 3;
                }
            }
        }

        return rsl;
    }

    bool TestOne(Dice* d, int oddGuy, bool heavier)
    {
        Init();
        bool fail = false;
        int rsl = 0;

        // first measure
        rsl = rsl*3 + 2 + OneMeasure(d, oddGuy, heavier, rsl, &fail);
        if (fail)
            return false;
        if (m_count[0]+m_count[1]+m_count[2] > 9)
            return false;

        // second measure
        rsl = rsl*3 + 2 + OneMeasure(d, oddGuy, heavier, rsl, &fail);
        if (fail)
            return false;
        if (m_count[0]+m_count[1]+m_count[2] > 3)
            return false;

        // third measure
        rsl = rsl*3 + 2 + OneMeasure(d, oddGuy, heavier, rsl, &fail);
        if (fail)
            return false;

        if (m_count[0]+m_count[1]+m_count[2] > 1)
            return false;
        else if (m_count[0]+m_count[1]+m_count[2] < 1)
        {
            printf("error! there is known to be one odd guy, %d %d %d\n", m_count[0], m_count[1], m_count[2]);
            Show();
        }

        return true;
    }

    void Show()
    {
        for (u8 i=0;  i < sc_nChoices;  i++)
            printf("%d:  %d %d %d %d  %d %d %d %d\n", i,
                   m_choice[i][0], m_choice[i][1], m_choice[i][2], m_choice[i][3],
                   m_choice[i][4], m_choice[i][5], m_choice[i][6], m_choice[i][7]);
        printf("\n");
    }

public:
    // test one weighing scheme
    static void Test(Dice* d, void *)
    {
        Island island;
        for (u8 i=sc_nGuys;  i--;)
        {
            if (!island.TestOne(d, i, true))
            {
                return;
            }
            if (!island.TestOne(d, i, false))
            {
                return;
            }
        }
        count_solutions++;
        if (!(count_solutions & (count_solutions-1)))
            island.Show();
    }
};


int main(int argc, const char** argv)
{
    Dice d;
    d.Exec(&Island::Test, 0);
    printf("%d\n", count_solutions);
    return 0;
}