#include <stdio.h>
#define PARTITION_MAX (10)
#define PARTITION_MIN (1)
#define SUCCESS (0)
#define ERR_BASE (0)
#define ERR_INPUT (ERR_BASE-1)
#define ERR_NULL (ERR_BASE-2)

void handle_err(int err) {
    if(err == ERR_INPUT) {
        printf("input should in [%d, %d]\n", PARTITION_MIN, PARTITION_MAX);
    } else {
    }
}

int
print_set(int *set, int n) {
    int i, part, is_first_set, is_first_num, max = 1;

    if(set == NULL)
        return ERR_NULL;

    for(i=1; i<=n; i++) {
        if(set[i] > max)
            max = set[i];
    }
    is_first_set = 1;
    for(part=1; part<=max; part++) {
        if(!is_first_set)
            printf(", {");
        else
            printf("{");
        is_first_num = 1;
        for(i=1; i<=n; i++) {
            if(set[i] == part) {
                if(!is_first_num)
                    printf(", ");
                printf("%d", i);
                is_first_num = 0;
            }
        }
        printf("}");
        is_first_set = 0;
    }
    printf("\n");

    return SUCCESS;
}

int
rec_part(int *set, int k, int m, int n, int *cnt)
{
    int i, ret;
    if(set == NULL) {
        return ERR_NULL;
    }

    if(k == n) {
        ret = print_set(set, n);
        (*cnt)++;
        return ret;
    }


    // k+1 items, m sets
    for(i=1; i<=m; i++) {
        set[k+1] = i;
        ret = rec_part(set, k+1, m, n, cnt);
        if(ret != SUCCESS)
            return ret;
    }

    // k+1 items, m+1 sets
    set[k+1] = m+1;
    ret = rec_part(set, k+1, m+1, n, cnt);

    return ret;
}

int
partition(int n)
{
    int set[PARTITION_MAX+1], i, cnt, ret;
    for(i=1; i<=n; i++)
        set[i] = 1;

    if(n > PARTITION_MAX || n < PARTITION_MIN) {
        return ERR_INPUT;
    }

    cnt = 0;
    ret = rec_part(set, 1, 1, n, &cnt);

    if(ret == SUCCESS)
        printf("\nresult: %d\n", cnt);

    return ret;
}

int
main()
{
    int n, ret;
    while(scanf("%d", &n) != EOF) {
        ret = partition(n);
        if(ret) {
            handle_err(ret);
        }
    }
    return 0;
}