data = {
    # 2-digit mappings
    "00": 1,
    "10": 1,
    "11": 2,
    "21": 1,
    "22": 1,
    # 4-digit mappings
    "0000": 540,
    "0010": 54,
    "1000": 54,
    "1010": 24,
    "1011": 114,
    "1110": 114,
    "1111": 720,
    "1121": 114,
    "2111": 114,
    "2121": 24,
    "2122": 54,
    "2221": 54,
    "2222": 540,
    # 6-digit mappings
    "000000": 1701000,
    "000010": 63000,
    "001000": 63000,
    "001010": 8640,
    "001110": 108360,
    "100000": 63000,
    "100010": 8640,
    "100011": 108360,
    "101000": 8640,
    "101010": 1080,
    "101011": 11160,
    "101110": 11160,
    "101111": 148680,
    "111000": 108360,
    "111010": 11160,
    "111011": 148680,
    "111110": 148680,
    "111111": 2041200,
    "111121": 148680,
    "112111": 148680,
    "112121": 11160,
    "112221": 108360,
    "211111": 148680,
    "211121": 11160,
    "211122": 108360,
    "212111": 11160,
    "212121": 1080,
    "212122": 8640,
    "212221": 8640,
    "212222": 63000,
    "222111": 108360,
    "222121": 8640,
    "222122": 63000,
    "222221": 63000,
    "222222": 1701000,
    # 8-digit mappings
    "00000000": 70251067,
    "00000010": 366735600,
    "00001000": 366735600,
    "00001010": 24494400,
    "00001110": 561330000,
    "00100000": 366735600,
    "00100010": 24494400,
    "00101000": 24494400,
    "00101010": 1260000,
    "00101110": 29484000,
    "00111000": 561330000,
    "00111010": 29484000,
    "00111110": 740955600,
    "10000000": 366735600,
    "10000010": 24494400,
    "10000011": 561330000,
    "10001000": 24494400,
    "10001010": 1260000,
    "10001011": 29484000,
    "10001110": 29484000,
    "10001111": 740955600,
    "10100000": 24494400,
    "10100010": 1260000,
    "10100011": 29484000,
    "10101000": 1260000,
    "10101010": 80640,
    "10101011": 1441440,
    "10101110": 1441440,
    "10101111": 34020000,
    "10111000": 29484000,
    "10111010": 1441440,
    "10111011": 34473600,
    "10111110": 34020000,
    "10111111": 905612400,
    "11100000": 561330000,
    "11100010": 29484000,
    "11100011": 740955600,
    "11101000": 29484000,
    "11101010": 1441440,
    "11101011": 34020000,
    "11101110": 34473600,
    "11101111": 905612400,
    "11111000": 740955600,
    "11111010": 34020000,
    "11111011": 905612400,
    "11111110": 905612400,
    "11111111": 794572653,
    "11111121": 905612400,
    "11112111": 905612400,
    "11112121": 34020000,
    "11112221": 740955600,
    "11211111": 905612400,
    "11211121": 34473600,
    "11212111": 34020000,
    "11212121": 1441440,
    "11212221": 29484000,
    "11222111": 740955600,
    "11222121": 29484000,
    "11222221": 561330000,
    "21111111": 905612400,
    "21111121": 34020000,
    "21111122": 740955600,
    "21112111": 34473600,
    "21112121": 1441440,
    "21112122": 29484000,
    "21112221": 29484000,
    "21112222": 561330000,
    "21211111": 34020000,
    "21211121": 1441440,
    "21211122": 29484000,
    "21212111": 1441440,
    "21212121": 80640,
    "21212122": 1260000,
    "21212221": 1260000,
    "21212222": 24494400,
    "21222111": 29484000,
    "21222121": 1260000,
    "21222122": 24494400,
    "21222221": 24494400,
    "21222222": 366735600,
    "22211111": 740955600,
    "22211121": 29484000,
    "22211122": 561330000,
    "22212111": 29484000,
    "22212121": 1260000,
    "22212122": 24494400,
    "22212221": 24494400,
    "22212222": 366735600,
    "22222111": 561330000,
    "22222121": 24494400,
    "22222122": 366735600,
    "22222221": 366735600,
    "22222222": 70251067,
    # 10-digit mappings
    "0000000000": 622541044,
    "0000000010": 101441660,
    "0000001000": 101441660,
    "0000001010": 534871773,
    "0000001110": 909454214,
    "0000100000": 101441660,
    "0000100010": 534871773,
    "0000101000": 534871773,
    "0000101010": 334711951,
    "0000101110": 399695486,
    "0000111000": 909454214,
    "0000111010": 399695486,
    "0000111110": 258171902,
    "0010000000": 101441660,
    "0010000010": 534871773,
    "0010001000": 534871773,
    "0010001010": 334711951,
    "0010001110": 399695486,
    "0010100000": 534871773,
    "0010100010": 334711951,
    "0010101000": 334711951,
    "0010101010": 228614400,
    "0010101110": 113089544,
    "0010111000": 399695486,
    "0010111010": 113089544,
    "0010111110": 540197620,
    "0011100000": 909454214,
    "0011100010": 399695486,
    "0011101000": 399695486,
    "0011101010": 113089544,
    "0011101110": 264519199,
    "0011111000": 258171902,
    "0011111010": 540197620,
    "0011111110": 147594738,
    "1000000000": 101441660,
    "1000000010": 534871773,
    "1000000011": 909454214,
    "1000001000": 534871773,
    "1000001010": 334711951,
    "1000001011": 399695486,
    "1000001110": 399695486,
    "1000001111": 258171902,
    "1000100000": 534871773,
    "1000100010": 334711951,
    "1000100011": 399695486,
    "1000101000": 334711951,
    "1000101010": 228614400,
    "1000101011": 113089544,
    "1000101110": 113089544,
    "1000101111": 540197620,
    "1000111000": 399695486,
    "1000111010": 113089544,
    "1000111011": 264519199,
    "1000111110": 540197620,
    "1000111111": 147594738,
    "1010000000": 534871773,
    "1010000010": 334711951,
    "1010000011": 399695486,
    "1010001000": 334711951,
    "1010001010": 228614400,
    "1010001011": 113089544,
    "1010001110": 113089544,
    "1010001111": 540197620,
    "1010100000": 334711951,
    "1010100010": 228614400,
    "1010100011": 113089544,
    "1010101000": 228614400,
    "1010101010": 9072000,
    "1010101011": 248572800,
    "1010101110": 248572800,
    "1010101111": 831591944,
    "1010111000": 113089544,
    "1010111010": 248572800,
    "1010111011": 891467144,
    "1010111110": 831591944,
    "1010111111": 956378175,
    "1011100000": 399695486,
    "1011100010": 113089544,
    "1011100011": 264519199,
    "1011101000": 113089544,
    "1011101010": 248572800,
    "1011101011": 891467144,
    "1011101110": 891467144,
    "1011101111": 405021333,
    "1011111000": 540197620,
    "1011111010": 831591944,
    "1011111011": 405021333,
    "1011111110": 956378175,
    "1011111111": 577722722,
    "1110000000": 909454214,
    "1110000010": 399695486,
    "1110000011": 258171902,
    "1110001000": 399695486,
    "1110001010": 113089544,
    "1110001011": 540197620,
    "1110001110": 264519199,
    "1110001111": 147594738,
    "1110100000": 399695486,
    "1110100010": 113089544,
    "1110100011": 540197620,
    "1110101000": 113089544,
    "1110101010": 248572800,
    "1110101011": 831591944,
    "1110101110": 891467144,
    "1110101111": 956378175,
    "1110111000": 264519199,
    "1110111010": 891467144,
    "1110111011": 405021333,
    "1110111110": 405021333,
    "1110111111": 577722722,
    "1111100000": 258171902,
    "1111100010": 540197620,
    "1111100011": 147594738,
    "1111101000": 540197620,
    "1111101010": 831591944,
    "1111101011": 956378175,
    "1111101110": 405021333,
    "1111101111": 577722722,
    "1111111000": 147594738,
    "1111111010": 956378175,
    "1111111011": 577722722,
    "1111111110": 577722722,
    "1111111111": 802823383,
    "1111111121": 577722722,
    "1111112111": 577722722,
    "1111112121": 956378175,
    "1111112221": 147594738,
    "1111211111": 577722722,
    "1111211121": 405021333,
    "1111212111": 956378175,
    "1111212121": 831591944,
    "1111212221": 540197620,
    "1111222111": 147594738,
    "1111222121": 540197620,
    "1111222221": 258171902,
    "1121111111": 577722722,
    "1121111121": 405021333,
    "1121112111": 405021333,
    "1121112121": 891467144,
    "1121112221": 264519199,
    "1121211111": 956378175,
    "1121211121": 891467144,
    "1121212111": 831591944,
    "1121212121": 248572800,
    "1121212221": 113089544,
    "1121222111": 540197620,
    "1121222121": 113089544,
    "1121222221": 399695486,
    "1122211111": 147594738,
    "1122211121": 264519199,
    "1122212111": 540197620,
    "1122212121": 113089544,
    "1122212221": 399695486,
    "1122222111": 258171902,
    "1122222121": 399695486,
    "1122222221": 909454214,
    "2111111111": 577722722,
    "2111111121": 956378175,
    "2111111122": 147594738,
    "2111112111": 405021333,
    "2111112121": 831591944,
    "2111112122": 540197620,
    "2111112221": 540197620,
    "2111112222": 258171902,
    "2111211111": 405021333,
    "2111211121": 891467144,
    "2111211122": 264519199,
    "2111212111": 891467144,
    "2111212121": 248572800,
    "2111212122": 113089544,
    "2111212221": 113089544,
    "2111212222": 399695486,
    "2111222111": 264519199,
    "2111222121": 113089544,
    "2111222122": 399695486,
    "2111222221": 399695486,
    "2111222222": 909454214,
    "2121111111": 956378175,
    "2121111121": 831591944,
    "2121111122": 540197620,
    "2121112111": 891467144,
    "2121112121": 248572800,
    "2121112122": 113089544,
    "2121112221": 113089544,
    "2121112222": 399695486,
    "2121211111": 831591944,
    "2121211121": 248572800,
    "2121211122": 113089544,
    "2121212111": 248572800,
    "2121212121": 9072000,
    "2121212122": 228614400,
    "2121212221": 228614400,
    "2121212222": 334711951,
    "2121222111": 113089544,
    "2121222121": 228614400,
    "2121222122": 334711951,
    "2121222221": 334711951,
    "2121222222": 534871773,
    "2122211111": 540197620,
    "2122211121": 113089544,
    "2122211122": 399695486,
    "2122212111": 113089544,
    "2122212121": 228614400,
    "2122212122": 334711951,
    "2122212221": 334711951,
    "2122212222": 534871773,
    "2122222111": 399695486,
    "2122222121": 334711951,
    "2122222122": 534871773,
    "2122222221": 534871773,
    "2122222222": 101441660,
    "2221111111": 147594738,
    "2221111121": 540197620,
    "2221111122": 258171902,
    "2221112111": 264519199,
    "2221112121": 113089544,
    "2221112122": 399695486,
    "2221112221": 399695486,
    "2221112222": 909454214,
    "2221211111": 540197620,
    "2221211121": 113089544,
    "2221211122": 399695486,
    "2221212111": 113089544,
    "2221212121": 228614400,
    "2221212122": 334711951,
    "2221212221": 334711951,
    "2221212222": 534871773,
    "2221222111": 399695486,
    "2221222121": 334711951,
    "2221222122": 534871773,
    "2221222221": 534871773,
    "2221222222": 101441660,
    "2222211111": 258171902,
    "2222211121": 399695486,
    "2222211122": 909454214,
    "2222212111": 399695486,
    "2222212121": 334711951,
    "2222212122": 534871773,
    "2222212221": 534871773,
    "2222212222": 101441660,
    "2222222111": 909454214,
    "2222222121": 534871773,
    "2222222122": 101441660,
    "2222222221": 101441660,
    "2222222222": 622541044,
    # 12-digit mappings
    "000000000000": 211803850,
    "000000000010": 938188926,
    "000000001000": 938188926,
    "000000001010": 633880533,
    "000000001110": 668799954,
    "000000100000": 938188926,
    "000000100010": 633880533,
    "000000101000": 633880533,
    "000000101010": 28833186,
    "000000101110": 974172069,
    "000000111000": 668799954,
    "000000111010": 974172069,
    "000000111110": 697953316,
    "000010000000": 938188926,
    "000010000010": 633880533,
    "000010001000": 633880533,
    "000010001010": 28833186,
    "000010001110": 974172069,
    "000010100000": 633880533,
    "000010100010": 28833186,
    "000010101000": 28833186,
    "000010101010": 992136520,
    "000010101110": 260883381,
    "000010111000": 974172069,
    "000010111010": 260883381,
    "000010111110": 770237731,
    "000011100000": 668799954,
    "000011100010": 974172069,
    "000011101000": 974172069,
    "000011101010": 260883381,
    "000011101110": 314463598,
    "000011111000": 697953316,
    "000011111010": 770237731,
    "000011111110": 25649005,
    "001000000000": 938188926,
    "001000000010": 633880533,
    "001000001000": 633880533,
    "001000001010": 28833186,
    "001000001110": 974172069,
    "001000100000": 633880533,
    "001000100010": 28833186,
    "001000101000": 28833186,
    "001000101010": 992136520,
    "001000101110": 260883381,
    "001000111000": 974172069,
    "001000111010": 260883381,
    "001000111110": 770237731,
    "001010000000": 633880533,
    "001010000010": 28833186,
    "001010001000": 28833186,
    "001010001010": 992136520,
    "001010001110": 260883381,
    "001010100000": 28833186,
    "001010100010": 992136520,
    "001010101000": 992136520,
    "001010101010": 809926036,
    "001010101110": 451431372,
    "001010111000": 260883381,
    "001010111010": 451431372,
    "001010111110": 655754154,
    "001011100000": 974172069,
    "001011100010": 260883381,
    "001011101000": 260883381,
    "001011101010": 451431372,
    "001011101110": 492933576,
    "001011111000": 770237731,
    "001011111010": 655754154,
    "001011111110": 22077519,
    "001110000000": 668799954,
    "001110000010": 974172069,
    "001110001000": 974172069,
    "001110001010": 260883381,
    "001110001110": 314463598,
    "001110100000": 974172069,
    "001110100010": 260883381,
    "001110101000": 260883381,
    "001110101010": 451431372,
    "001110101110": 492933576,
    "001110111000": 314463598,
    "001110111010": 492933576,
    "001110111110": 110529260,
    "001111100000": 697953316,
    "001111100010": 770237731,
    "001111101000": 770237731,
    "001111101010": 655754154,
    "001111101110": 110529260,
    "001111111000": 25649005,
    "001111111010": 22077519,
    "001111111110": 651887035,
    "100000000000": 938188926,
    "100000000010": 633880533,
    "100000000011": 668799954,
    "100000001000": 633880533,
    "100000001010": 28833186,
    "100000001011": 974172069,
    "100000001110": 974172069,
    "100000001111": 697953316,
    "100000100000": 633880533,
    "100000100010": 28833186,
    "100000100011": 974172069,
    "100000101000": 28833186,
    "100000101010": 992136520,
    "100000101011": 260883381,
    "100000101110": 260883381,
    "100000101111": 770237731,
    "100000111000": 974172069,
    "100000111010": 260883381,
    "100000111011": 314463598,
    "100000111110": 770237731,
    "100000111111": 25649005,
    "100010000000": 633880533,
    "100010000010": 28833186,
    "100010000011": 974172069,
    "100010001000": 28833186,
    "100010001010": 992136520,
    "100010001011": 260883381,
    "100010001110": 260883381,
    "100010001111": 770237731,
    "100010100000": 28833186,
    "100010100010": 992136520,
    "100010100011": 260883381,
    "100010101000": 992136520,
    "100010101010": 809926036,
    "100010101011": 451431372,
    "100010101110": 451431372,
    "100010101111": 655754154,
    "100010111000": 260883381,
    "100010111010": 451431372,
    "100010111011": 492933576,
    "100010111110": 655754154,
    "100010111111": 22077519,
    "100011100000": 974172069,
    "100011100010": 260883381,
    "100011100011": 314463598,
    "100011101000": 260883381,
    "100011101010": 451431372,
    "100011101011": 492933576,
    "100011101110": 492933576,
    "100011101111": 110529260,
    "100011111000": 770237731,
    "100011111010": 655754154,
    "100011111011": 110529260,
    "100011111110": 22077519,
    "100011111111": 651887035,
    "101000000000": 633880533,
    "101000000010": 28833186,
    "101000000011": 974172069,
    "101000001000": 28833186,
    "101000001010": 992136520,
    "101000001011": 260883381,
    "101000001110": 260883381,
    "101000001111": 770237731,
    "101000100000": 28833186,
    "101000100010": 992136520,
    "101000100011": 260883381,
    "101000101000": 992136520,
    "101000101010": 809926036,
    "101000101011": 451431372,
    "101000101110": 451431372,
    "101000101111": 655754154,
    "101000111000": 260883381,
    "101000111010": 451431372,
    "101000111011": 492933576,
    "101000111110": 655754154,
    "101000111111": 22077519,
    "101010000000": 28833186,
    "101010000010": 992136520,
    "101010000011": 260883381,
    "101010001000": 992136520,
    "101010001010": 809926036,
    "101010001011": 451431372,
    "101010001110": 451431372,
    "101010001111": 655754154,
    "101010100000": 992136520,
    "101010100010": 809926036,
    "101010100011": 451431372,
    "101010101000": 809926036,
    "101010101010": 437004793,
    "101010101011": 923436415,
    "101010101110": 923436415,
    "101010101111": 13439901,
    "101010111000": 451431372,
    "101010111010": 923436415,
    "101010111011": 910726231,
    "101010111110": 13439901,
    "101010111111": 213445498,
    "101011100000": 260883381,
    "101011100010": 451431372,
    "101011100011": 492933576,
    "101011101000": 451431372,
    "101011101010": 923436415,
    "101011101011": 910726231,
    "101011101110": 910726231,
    "101011101111": 887804349,
    "101011111000": 655754154,
    "101011111010": 13439901,
    "101011111011": 887804349,
    "101011111110": 213445498,
    "101011111111": 729691447,
    "101110000000": 974172069,
    "101110000010": 260883381,
    "101110000011": 314463598,
    "101110001000": 260883381,
    "101110001010": 451431372,
    "101110001011": 492933576,
    "101110001110": 492933576,
    "101110001111": 110529260,
    "101110100000": 260883381,
    "101110100010": 451431372,
    "101110100011": 492933576,
    "101110101000": 451431372,
    "101110101010": 923436415,
    "101110101011": 910726231,
    "101110101110": 910726231,
    "101110101111": 887804349,
    "101110111000": 492933576,
    "101110111010": 910726231,
    "101110111011": 724983771,
    "101110111110": 887804349,
    "101110111111": 362369055,
    "101111100000": 770237731,
    "101111100010": 655754154,
    "101111100011": 110529260,
    "101111101000": 655754154,
    "101111101010": 13439901,
    "101111101011": 887804349,
    "101111101110": 887804349,
    "101111101111": 906594929,
    "101111111000": 22077519,
    "101111111010": 213445498,
    "101111111011": 362369055,
    "101111111110": 729691447,
    "101111111111": 576667392,
    "111000000000": 668799954,
    "111000000010": 974172069,
    "111000000011": 697953316,
    "111000001000": 974172069,
    "111000001010": 260883381,
    "111000001011": 770237731,
    "111000001110": 314463598,
    "111000001111": 25649005,
    "111000100000": 974172069,
    "111000100010": 260883381,
    "111000100011": 770237731,
    "111000101000": 260883381,
    "111000101010": 451431372,
    "111000101011": 655754154,
    "111000101110": 492933576,
    "111000101111": 22077519,
    "111000111000": 314463598,
    "111000111010": 492933576,
    "111000111011": 110529260,
    "111000111110": 110529260,
    "111000111111": 651887035,
    "111010000000": 974172069,
    "111010000010": 260883381,
    "111010000011": 770237731,
    "111010001000": 260883381,
    "111010001010": 451431372,
    "111010001011": 655754154,
    "111010001110": 492933576,
    "111010001111": 22077519,
    "111010100000": 260883381,
    "111010100010": 451431372,
    "111010100011": 655754154,
    "111010101000": 451431372,
    "111010101010": 923436415,
    "111010101011": 13439901,
    "111010101110": 910726231,
    "111010101111": 213445498,
    "111010111000": 492933576,
    "111010111010": 910726231,
    "111010111011": 887804349,
    "111010111110": 887804349,
    "111010111111": 729691447,
    "111011100000": 314463598,
    "111011100010": 492933576,
    "111011100011": 110529260,
    "111011101000": 492933576,
    "111011101010": 910726231,
    "111011101011": 887804349,
    "111011101110": 724983771,
    "111011101111": 362369055,
    "111011111000": 110529260,
    "111011111010": 887804349,
    "111011111011": 906594929,
    "111011111110": 362369055,
    "111011111111": 576667392,
    "111110000000": 697953316,
    "111110000010": 770237731,
    "111110000011": 25649005,
    "111110001000": 770237731,
    "111110001010": 655754154,
    "111110001011": 22077519,
    "111110001110": 110529260,
    "111110001111": 651887035,
    "111110100000": 770237731,
    "111110100010": 655754154,
    "111110100011": 22077519,
    "111110101000": 655754154,
    "111110101010": 13439901,
    "111110101011": 213445498,
    "111110101110": 887804349,
    "111110101111": 729691447,
    "111110111000": 110529260,
    "111110111010": 887804349,
    "111110111011": 362369055,
    "111110111110": 906594929,
    "111110111111": 576667392,
    "111111100000": 25649005,
    "111111100010": 22077519,
    "111111100011": 651887035,
    "111111101000": 22077519,
    "111111101010": 213445498,
    "111111101011": 729691447,
    "111111101110": 362369055,
    "111111101111": 576667392,
    "111111111000": 651887035,
    "111111111010": 729691447,
    "111111111011": 576667392,
    "111111111110": 576667392,
    "111111111111": 321967837,
    "111111111121": 576667392,
    "111111112111": 576667392,
    "111111112121": 729691447,
    "111111112221": 651887035,
    "111111211111": 576667392,
    "111111211121": 362369055,
    "111111212111": 729691447,
    "111111212121": 213445498,
    "111111212221": 22077519,
    "111111222111": 651887035,
    "111111222121": 22077519,
    "111111222221": 25649005,
    "111121111111": 576667392,
    "111121111121": 906594929,
    "111121112111": 362369055,
    "111121112121": 887804349,
    "111121112221": 110529260,
    "111121211111": 729691447,
    "111121211121": 887804349,
    "111121212111": 213445498,
    "111121212121": 13439901,
    "111121212221": 655754154,
    "111121222111": 22077519,
    "111121222121": 655754154,
    "111121222221": 770237731,
    "111122211111": 651887035,
    "111122211121": 110529260,
    "111122212111": 22077519,
    "111122212121": 655754154,
    "111122212221": 770237731,
    "111122222111": 25649005,
    "111122222121": 770237731,
    "111122222221": 697953316,
    "112111111111": 576667392,
    "112111111121": 362369055,
    "112111112111": 906594929,
    "112111112121": 887804349,
    "112111112221": 110529260,
    "112111211111": 362369055,
    "112111211121": 724983771,
    "112111212111": 887804349,
    "112111212121": 910726231,
    "112111212221": 492933576,
    "112111222111": 110529260,
    "112111222121": 492933576,
    "112111222221": 314463598,
    "112121111111": 729691447,
    "112121111121": 887804349,
    "112121112111": 887804349,
    "112121112121": 910726231,
    "112121112221": 492933576,
    "112121211111": 213445498,
    "112121211121": 910726231,
    "112121212111": 13439901,
    "112121212121": 923436415,
    "112121212221": 451431372,
    "112121222111": 655754154,
    "112121222121": 451431372,
    "112121222221": 260883381,
    "112122211111": 22077519,
    "112122211121": 492933576,
    "112122212111": 655754154,
    "112122212121": 451431372,
    "112122212221": 260883381,
    "112122222111": 770237731,
    "112122222121": 260883381,
    "112122222221": 974172069,
    "112221111111": 651887035,
    "112221111121": 110529260,
    "112221112111": 110529260,
    "112221112121": 492933576,
    "112221112221": 314463598,
    "112221211111": 22077519,
    "112221211121": 492933576,
    "112221212111": 655754154,
    "112221212121": 451431372,
    "112221212221": 260883381,
    "112221222111": 770237731,
    "112221222121": 260883381,
    "112221222221": 974172069,
    "112222211111": 25649005,
    "112222211121": 314463598,
    "112222212111": 770237731,
    "112222212121": 260883381,
    "112222212221": 974172069,
    "112222222111": 697953316,
    "112222222121": 974172069,
    "112222222221": 668799954,
    "211111111111": 576667392,
    "211111111121": 729691447,
    "211111111122": 651887035,
    "211111112111": 362369055,
    "211111112121": 213445498,
    "211111112122": 22077519,
    "211111112221": 22077519,
    "211111112222": 25649005,
    "211111211111": 906594929,
    "211111211121": 887804349,
    "211111211122": 110529260,
    "211111212111": 887804349,
    "211111212121": 13439901,
    "211111212122": 655754154,
    "211111212221": 655754154,
    "211111212222": 770237731,
    "211111222111": 110529260,
    "211111222121": 655754154,
    "211111222122": 770237731,
    "211111222221": 770237731,
    "211111222222": 697953316,
    "211121111111": 362369055,
    "211121111121": 887804349,
    "211121111122": 110529260,
    "211121112111": 724983771,
    "211121112121": 910726231,
    "211121112122": 492933576,
    "211121112221": 492933576,
    "211121112222": 314463598,
    "211121211111": 887804349,
    "211121211121": 910726231,
    "211121211122": 492933576,
    "211121212111": 910726231,
    "211121212121": 923436415,
    "211121212122": 451431372,
    "211121212221": 451431372,
    "211121212222": 260883381,
    "211121222111": 492933576,
    "211121222121": 451431372,
    "211121222122": 260883381,
    "211121222221": 260883381,
    "211121222222": 974172069,
    "211122211111": 110529260,
    "211122211121": 492933576,
    "211122211122": 314463598,
    "211122212111": 492933576,
    "211122212121": 451431372,
    "211122212122": 260883381,
    "211122212221": 260883381,
    "211122212222": 974172069,
    "211122222111": 314463598,
    "211122222121": 260883381,
    "211122222122": 974172069,
    "211122222221": 974172069,
    "211122222222": 668799954,
    "212111111111": 729691447,
    "212111111121": 213445498,
    "212111111122": 22077519,
    "212111112111": 887804349,
    "212111112121": 13439901,
    "212111112122": 655754154,
    "212111112221": 655754154,
    "212111112222": 770237731,
    "212111211111": 887804349,
    "212111211121": 910726231,
    "212111211122": 492933576,
    "212111212111": 910726231,
    "212111212121": 923436415,
    "212111212122": 451431372,
    "212111212221": 451431372,
    "212111212222": 260883381,
    "212111222111": 492933576,
    "212111222121": 451431372,
    "212111222122": 260883381,
    "212111222221": 260883381,
    "212111222222": 974172069,
    "212121111111": 213445498,
    "212121111121": 13439901,
    "212121111122": 655754154,
    "212121112111": 910726231,
    "212121112121": 923436415,
    "212121112122": 451431372,
    "212121112221": 451431372,
    "212121112222": 260883381,
    "212121211111": 13439901,
    "212121211121": 923436415,
    "212121211122": 451431372,
    "212121212111": 923436415,
    "212121212121": 437004793,
    "212121212122": 809926036,
    "212121212221": 809926036,
    "212121212222": 992136520,
    "212121222111": 451431372,
    "212121222121": 809926036,
    "212121222122": 992136520,
    "212121222221": 992136520,
    "212121222222": 28833186,
    "212122211111": 655754154,
    "212122211121": 451431372,
    "212122211122": 260883381,
    "212122212111": 451431372,
    "212122212121": 809926036,
    "212122212122": 992136520,
    "212122212221": 992136520,
    "212122212222": 28833186,
    "212122222111": 260883381,
    "212122222121": 992136520,
    "212122222122": 28833186,
    "212122222221": 28833186,
    "212122222222": 633880533,
    "212221111111": 22077519,
    "212221111121": 655754154,
    "212221111122": 770237731,
    "212221112111": 492933576,
    "212221112121": 451431372,
    "212221112122": 260883381,
    "212221112221": 260883381,
    "212221112222": 974172069,
    "212221211111": 655754154,
    "212221211121": 451431372,
    "212221211122": 260883381,
    "212221212111": 451431372,
    "212221212121": 809926036,
    "212221212122": 992136520,
    "212221212221": 992136520,
    "212221212222": 28833186,
    "212221222111": 260883381,
    "212221222121": 992136520,
    "212221222122": 28833186,
    "212221222221": 28833186,
    "212221222222": 633880533,
    "212222211111": 770237731,
    "212222211121": 260883381,
    "212222211122": 974172069,
    "212222212111": 260883381,
    "212222212121": 992136520,
    "212222212122": 28833186,
    "212222212221": 28833186,
    "212222212222": 633880533,
    "212222222111": 974172069,
    "212222222121": 28833186,
    "212222222122": 633880533,
    "212222222221": 633880533,
    "212222222222": 938188926,
    "222111111111": 651887035,
    "222111111121": 22077519,
    "222111111122": 25649005,
    "222111112111": 110529260,
    "222111112121": 655754154,
    "222111112122": 770237731,
    "222111112221": 770237731,
    "222111112222": 697953316,
    "222111211111": 110529260,
    "222111211121": 492933576,
    "222111211122": 314463598,
    "222111212111": 492933576,
    "222111212121": 451431372,
    "222111212122": 260883381,
    "222111212221": 260883381,
    "222111212222": 974172069,
    "222111222111": 314463598,
    "222111222121": 260883381,
    "222111222122": 974172069,
    "222111222221": 974172069,
    "222111222222": 668799954,
    "222121111111": 22077519,
    "222121111121": 655754154,
    "222121111122": 770237731,
    "222121112111": 492933576,
    "222121112121": 451431372,
    "222121112122": 260883381,
    "222121112221": 260883381,
    "222121112222": 974172069,
    "222121211111": 655754154,
    "222121211121": 451431372,
    "222121211122": 260883381,
    "222121211121": 451431372,
    "222121212121": 809926036,
    "222121212122": 992136520,
    "222121212221": 992136520,
    "222121212222": 28833186,
    "222121222111": 260883381,
    "222121222121": 992136520,
    "222121222122": 28833186,
    "222121222221": 28833186,
    "222121222222": 633880533,
    "222122211111": 770237731,
    "222122211121": 260883381,
    "222122211122": 974172069,
    "222122212111": 260883381,
    "222122212121": 992136520,
    "222122212122": 28833186,
    "222122212221": 28833186,
    "222122212222": 633880533,
    "222122222111": 974172069,
    "222122222121": 28833186,
    "222122222122": 633880533,
    "222122222221": 633880533,
    "222122222222": 938188926,
    "222221111111": 25649005,
    "222221111121": 770237731,
    "222221111122": 697953316,
    "222221112111": 314463598,
    "222221112121": 260883381,
    "222221112122": 974172069,
    "222221112221": 974172069,
    "222221112222": 668799954,
    "222221211111": 770237731,
    "222221211121": 260883381,
    "222221211122": 974172069,
    "222221211121": 260883381,
    "222221212121": 992136520,
    "222221212122": 28833186,
    "222221212221": 28833186,
    "222221212222": 633880533,
    "222221222111": 974172069,
    "222221222121": 28833186,
    "222221222122": 633880533,
    "222221222221": 633880533,
    "222221222222": 938188926,
    "222222211111": 697953316,
    "222222211121": 974172069,
    "222222211122": 668799954,
    "222222212111": 974172069,
    "222222212121": 28833186,
    "222222212122": 633880533,
    "222222212221": 633880533,
    "222222212222": 938188926,
    "222222222111": 668799954,
    "222222222121": 633880533,
    "222222222122": 938188926,
    "222222222221": 938188926,
    "222222222222": 211803850,
}

line1 = input().strip()

num_queries = int(line1)

for _ in range(num_queries):
    n = input()
    sequence_raw = input().strip()
    key = sequence_raw.replace(" ", "")

    if int(n) == 7:
        print(256223893)
    else:
        print(data.get(key, 0))