Merge pull request #1523 from dcw803/master

imported my solutions to challenge-054

4 files changed, 234 insertions, 35 deletions

diff --git a/challenge-054/duncan-c-white/README b/challenge-054/duncan-c-white/README
index 1f9e9e20df..f38b0532e4 100644
--- a/challenge-054/duncan-c-white/README
+++ b/challenge-054/duncan-c-white/README
@@ -1,52 +1,56 @@
-Task 1: "Rotate Matrix
+Task 1: "kth Permutation Sequence
 
-Write a script to rotate the followin matrix by given 90/180/270 degrees clockwise.
+Write a script to accept two integers n (>=1) and k (>=1). It should
+print the kth permutation of n integers. For more information, please
+follow the wiki page 
 
-[ 1, 2, 3 ]
-[ 4, 5, 6 ]
-[ 7, 8, 9 ]
+	https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
 
-For example, if you rotate by 90 degrees then expected result should be like below
+(in summary: 'in other words, these k-permutations of n are the different
+ordered arrangements of a k-element subset of an n-set (sometimes called
+variations or 'arrangements' in the older literature.')
 
-[ 7, 4, 1 ]
-[ 8, 5, 2 ]
-[ 9, 6, 3 ]
-"
+For example, n=3 and k=4, the possible permutation sequences are listed below:
 
-My notes: sounds pretty trivial.  Made slightly cuter by an inline package in order
-to use classic Perl OO in order to get autostringification.
+123
+132
+213
+231
+312
+321
 
+The script should print the 4th permutation sequence 231.
+"
 
-Task 2: "Vowel Strings
+My notes: The wiki definition describes a LIST of all k-from-n partial
+permutations, whereas the example shows something different: generate a
+single permutation: the Kth complete permutation sequence of 1..N.  So
+ignore the wiki, and go with the example.  Obvious method: generate all
+permutations of 1..N in the above order, then pick the Kth one.  But can
+we directly generate the Kth permutation?  After a bit of thought: yes we can.
 
-Write a script to accept an integer 1 <= N <= 5 that would print all
-possible strings of size N formed by using only vowels (a, e, i, o, u).
 
-The string should follow the following rules:
+Task 2: "Collatz Conjecture
 
-    'a' can only be followed by 'e' and 'i'.
+It is thought that the following sequence will always reach 1:
 
-    'e' can only be followed by 'i'.
+    $n = $n / 2 when $n is even
+    $n = 3*$n + 1 when $n is odd
 
-    'i' can only be followed by 'a', 'e', 'o', and 'u'.
+For example, if we start at 23, we get the following sequence:
 
-    'o' can only be followed by 'a' and 'u'.
+	23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
 
-    'u' can only be followed by 'o' and 'e'.
+Write a function that finds the Collatz sequence for any positive
+integer. Notice how the sequence itself may go far above the
+original starting number.
 
-For example, if the given integer N = 2 then script should print the following strings:
+Extra Credit
 
-ae
-ai
-ei
-ia
-io
-iu
-ie
-oa
-ou
-uo
-ue
-"
+Have your script calculate the sequence length for all starting numbers
+up to 1000000 (1e6), and output the starting number and sequence length
+for the longest 20 sequences."
 
-My notes: reading "and" as "or" above, it sounds pretty simple as a generator.
+My notes: Sounds interesting!  For the extra credit question, you can find the
+"longest 20 sequences for N up to 1e6" output in ch-2:-100000.output.  The
+longest sequence is of length 351.
diff --git a/challenge-054/duncan-c-white/perl/ch-1.pl b/challenge-054/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..da06c05d21
--- /dev/null
+++ b/challenge-054/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,90 @@
+#!/usr/bin/perl
+#
+# Task 1: "kth Permutation Sequence
+#
+# Write a script to accept two integers n (>=1) and k (>=1). It should
+# print the kth permutation of n integers. For more information, please
+# follow the wiki page 
+# 
+# 	https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
+# 
+# (in summary: 'in other words, these k-permutations of n are the different
+# ordered arrangements of a k-element subset of an n-set (sometimes called
+# variations or 'arrangements' in the older literature.')
+# 
+# For example, n=3 and k=4, the possible permutation sequences are listed below:
+# 
+# 123
+# 132
+# 213
+# 231
+# 312
+# 321
+# 
+# The script should print the 4th permutation sequence 231.
+# "
+# 
+# My notes: The wiki definition defines k-from-n permutations as a LIST of
+# all k-from-n partial permutations, whereas the example above shows something
+# different: generate a single permutation: the Kth complete permutation
+# sequence of 1..N.  So let's ignore the wiki, and go with the example.
+# Obvious method: generate all permutations of 1..N in the above order, then
+# pick the Kth one.  But that sounds roundabout.  Can we directly generate the
+# Kth permutation I wonder?  After a bit of thought: yes we can.
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+use Function::Parameters;
+#use Data::Dumper;
+
+die "Usage: kth-perm-n k n\n" unless @ARGV == 2;
+
+my( $k, $n ) = @ARGV;
+die "kth-perm-n: n $n must be range 1..\n" unless $n>=1;
+
+my $nperms = fact( $n );
+die "kth-perm-n: k $k must be range 1..$nperms\n" unless $k>=1 && $k<=$nperms;
+
+my $alldigits = join('', 1..$n);
+my $permstr = nthperm( $k-1, $alldigits, $n, $nperms );
+say "${k}th perm of $alldigits is $permstr";
+
+#
+# my $permstr = nthperm( $permno, $alldigits, $n, $nperms );
+#	Return the $permno'th permutation (range 0..$nperms-1)
+#	of $alldigits (length $n).
+#
+fun nthperm( $permno, $alldigits, $n, $nperms )
+{
+	if( $n==1 )
+	{
+		return substr( $alldigits, $permno, 1 );
+	}
+	my $w = $nperms / $n;
+
+	my $firstdigit = substr( $alldigits, int($permno/$w), 1 );
+	my $permstr = $firstdigit;
+	$alldigits =~ s/$firstdigit//;
+	$permstr .= nthperm( $permno%$w, $alldigits, $n-1, $nperms/$n );
+	return $permstr;
+}
+
+
+
+
+#
+# my $fact = fact( $n );
+#	Calculate n!
+#
+fun fact( $n )
+{
+	my $result = 1;
+	$result *= $_ for 1..$n;
+	return $result;
+}
+
+
+
+
diff --git a/challenge-054/duncan-c-white/perl/ch-2.pl b/challenge-054/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..f0ca90f98d
--- /dev/null
+++ b/challenge-054/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,84 @@
+#!/usr/bin/perl
+#
+# Task 2: "Collatz Conjecture
+#
+# It is thought that the following sequence will always reach 1:
+# 
+#     $n = $n / 2 when $n is even
+#     $n = 3*$n + 1 when $n is odd
+# 
+# For example, if we start at 23, we get the following sequence:
+# 
+# 	23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
+# 
+# Write a function that finds the Collatz sequence for any positive
+# integer. Notice how the sequence itself may go far above the
+# original starting number.
+# 
+# Extra Credit
+# 
+# Have your script calculate the sequence length for all starting numbers
+# up to 1000000 (1e6), and output the starting number and sequence length
+# for the longest 20 sequences."
+# 
+# My notes: Sounds interesting!
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+
+die "Usage: collatz N(>0) or -N [meaning do for all N=1..10^6]\n"
+	unless @ARGV==1;
+my $n = shift;
+
+if( $n>0 )
+{
+	my @seq = collatz( $n );
+	say "collatz $n = ", join(',', @seq);
+} else
+{
+	# find longest 20 sequences for x=1..n
+	my @longest20;	# array of [ len, sequence ]
+
+	foreach my $x (1..-$n)
+	{
+		my @seq = collatz( $x );
+		my $len = @seq;
+		push @longest20, [ $len, @seq ];
+		@longest20 = sort { $b->[0] <=> $a->[0] } @longest20;
+		$#longest20 = 19 if @longest20>20;
+		#say "x=$x longest: ", join(',',@$_) for @longest20;
+	}
+
+	say "longest 20 collatz sequences:";
+	foreach my $longest (@longest20)
+	{
+		my( $len, @seq ) = @$longest;
+		say "len=$len: ", join(',',@seq);
+	}
+}
+
+
+#
+# my @seq = collatz( $n );
+#	Generate the collatz sequence for $n.
+#	Rules are:
+#		stop when $n==1
+#		$n = $n / 2 when $n is even
+#		$n = 3*$n + 1 when $n is odd
+# 
+#
+fun collatz( $n )
+{
+	my @seq = ( $n );
+	while( $n != 1 )
+	{
+		if( $n%2==0 ) { $n = $n / 2 } else { $n = 3*$n + 1 }
+		push @seq, $n;
+	}
+	return @seq;
+}
diff --git a/challenge-054/duncan-c-white/perl/ch-2:-100000.output b/challenge-054/duncan-c-white/perl/ch-2:-100000.output
new file mode 100644
index 0000000000..763e0de26a
--- /dev/null
+++ b/challenge-054/duncan-c-white/perl/ch-2:-100000.output
@@ -0,0 +1,21 @@
+longest 20 collatz sequences:
+len=351: 77031,231094,115547,346642,173321,519964,259982,129991,389974,194987,584962,292481,877444,438722,219361,658084,329042,164521,493564,246782,123391,370174,185087,555262,277631,832894,416447,1249342,624671,1874014,937007,2811022,1405511,4216534,2108267,6324802,3162401,9487204,4743602,2371801,7115404,3557702,1778851,5336554,2668277,8004832,4002416,2001208,1000604,500302,250151,750454,375227,1125682,562841,1688524,844262,422131,1266394,633197,1899592,949796,474898,237449,712348,356174,178087,534262,267131,801394,400697,1202092,601046,300523,901570,450785,1352356,676178,338089,1014268,507134,253567,760702,380351,1141054,570527,1711582,855791,2567374,1283687,3851062,1925531,5776594,2888297,8664892,4332446,2166223,6498670,3249335,9748006,4874003,14622010,7311005,21933016,10966508,5483254,2741627,8224882,4112441,12337324,6168662,3084331,9252994,4626497,13879492,6939746,3469873,10409620,5204810,2602405,7807216,3903608,1951804,975902,487951,1463854,731927,2195782,1097891,3293674,1646837,4940512,2470256,1235128,617564,308782,154391,463174,231587,694762,347381,1042144,521072,260536,130268,65134,32567,97702,48851,146554,73277,219832,109916,54958,27479,82438,41219,123658,61829,185488,92744,46372,23186,11593,34780,17390,8695,26086,13043,39130,19565,58696,29348,14674,7337,22012,11006,5503,16510,8255,24766,12383,37150,18575,55726,27863,83590,41795,125386,62693,188080,94040,47020,23510,11755,35266,17633,52900,26450,13225,39676,19838,9919,29758,14879,44638,22319,66958,33479,100438,50219,150658,75329,225988,112994,56497,169492,84746,42373,127120,63560,31780,15890,7945,23836,11918,5959,17878,8939,26818,13409,40228,20114,10057,30172,15086,7543,22630,11315,33946,16973,50920,25460,12730,6365,19096,9548,4774,2387,7162,3581,10744,5372,2686,1343,4030,2015,6046,3023,9070,4535,13606,6803,20410,10205,30616,15308,7654,3827,11482,5741,17224,8612,4306,2153,6460,3230,1615,4846,2423,7270,3635,10906,5453,16360,8180,4090,2045,6136,3068,1534,767,2302,1151,3454,1727,5182,2591,7774,3887,11662,5831,17494,8747,26242,13121,39364,19682,9841,29524,14762,7381,22144,11072,5536,2768,1384,692,346,173,520,260,130,65,196,98,49,148,74,37,112,56,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=340: 52527,157582,78791,236374,118187,354562,177281,531844,265922,132961,398884,199442,99721,299164,149582,74791,224374,112187,336562,168281,504844,252422,126211,378634,189317,567952,283976,141988,70994,35497,106492,53246,26623,79870,39935,119806,59903,179710,89855,269566,134783,404350,202175,606526,303263,909790,454895,1364686,682343,2047030,1023515,3070546,1535273,4605820,2302910,1151455,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=338: 78791,236374,118187,354562,177281,531844,265922,132961,398884,199442,99721,299164,149582,74791,224374,112187,336562,168281,504844,252422,126211,378634,189317,567952,283976,141988,70994,35497,106492,53246,26623,79870,39935,119806,59903,179710,89855,269566,134783,404350,202175,606526,303263,909790,454895,1364686,682343,2047030,1023515,3070546,1535273,4605820,2302910,1151455,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=335: 60975,182926,91463,274390,137195,411586,205793,617380,308690,154345,463036,231518,115759,347278,173639,520918,260459,781378,390689,1172068,586034,293017,879052,439526,219763,659290,329645,988936,494468,247234,123617,370852,185426,92713,278140,139070,69535,208606,104303,312910,156455,469366,234683,704050,352025,1056076,528038,264019,792058,396029,1188088,594044,297022,148511,445534,222767,668302,334151,1002454,501227,1503682,751841,2255524,1127762,563881,1691644,845822,422911,1268734,634367,1903102,951551,2854654,1427327,4281982,2140991,6422974,3211487,9634462,4817231,14451694,7225847,21677542,10838771,32516314,16258157,48774472,24387236,12193618,6096809,18290428,9145214,4572607,13717822,6858911,20576734,10288367,30865102,15432551,46297654,23148827,69446482,34723241,104169724,52084862,26042431,78127294,39063647,117190942,58595471,175786414,87893207,263679622,131839811,395519434,197759717,593279152,296639576,148319788,74159894,37079947,111239842,55619921,166859764,83429882,41714941,125144824,62572412,31286206,15643103,46929310,23464655,70393966,35196983,105590950,52795475,158386426,79193213,237579640,118789820,59394910,29697455,89092366,44546183,133638550,66819275,200457826,100228913,300686740,150343370,75171685,225515056,112757528,56378764,28189382,14094691,42284074,21142037,63426112,31713056,15856528,7928264,3964132,1982066,991033,2973100,1486550,743275,2229826,1114913,3344740,1672370,836185,2508556,1254278,627139,1881418,940709,2822128,1411064,705532,352766,176383,529150,264575,793726,396863,1190590,595295,1785886,892943,2678830,1339415,4018246,2009123,6027370,3013685,9041056,4520528,2260264,1130132,565066,282533,847600,423800,211900,105950,52975,158926,79463,238390,119195,357586,178793,536380,268190,134095,402286,201143,603430,301715,905146,452573,1357720,678860,339430,169715,509146,254573,763720,381860,190930,95465,286396,143198,71599,214798,107399,322198,161099,483298,241649,724948,362474,181237,543712,271856,135928,67964,33982,16991,50974,25487,76462,38231,114694,57347,172042,86021,258064,129032,64516,32258,16129,48388,24194,12097,36292,18146,9073,27220,13610,6805,20416,10208,5104,2552,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=333: 87087,261262,130631,391894,195947,587842,293921,881764,440882,220441,661324,330662,165331,495994,247997,743992,371996,185998,92999,278998,139499,418498,209249,627748,313874,156937,470812,235406,117703,353110,176555,529666,264833,794500,397250,198625,595876,297938,148969,446908,223454,111727,335182,167591,502774,251387,754162,377081,1131244,565622,282811,848434,424217,1272652,636326,318163,954490,477245,1431736,715868,357934,178967,536902,268451,805354,402677,1208032,604016,302008,151004,75502,37751,113254,56627,169882,84941,254824,127412,63706,31853,95560,47780,23890,11945,35836,17918,8959,26878,13439,40318,20159,60478,30239,90718,45359,136078,68039,204118,102059,306178,153089,459268,229634,114817,344452,172226,86113,258340,129170,64585,193756,96878,48439,145318,72659,217978,108989,326968,163484,81742,40871,122614,61307,183922,91961,275884,137942,68971,206914,103457,310372,155186,77593,232780,116390,58195,174586,87293,261880,130940,65470,32735,98206,49103,147310,73655,220966,110483,331450,165725,497176,248588,124294,62147,186442,93221,279664,139832,69916,34958,17479,52438,26219,78658,39329,117988,58994,29497,88492,44246,22123,66370,33185,99556,49778,24889,74668,37334,18667,56002,28001,84004,42002,21001,63004,31502,15751,47254,23627,70882,35441,106324,53162,26581,79744,39872,19936,9968,4984,2492,1246,623,1870,935,2806,1403,4210,2105,6316,3158,1579,4738,2369,7108,3554,1777,5332,2666,1333,4000,2000,1000,500,250,125,376,188,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=333: 88059,264178,132089,396268,198134,99067,297202,148601,445804,222902,111451,334354,167177,501532,250766,125383,376150,188075,564226,282113,846340,423170,211585,634756,317378,158689,476068,238034,119017,357052,178526,89263,267790,133895,401686,200843,602530,301265,903796,451898,225949,677848,338924,169462,84731,254194,127097,381292,190646,95323,285970,142985,428956,214478,107239,321718,160859,482578,241289,723868,361934,180967,542902,271451,814354,407177,1221532,610766,305383,916150,458075,1374226,687113,2061340,1030670,515335,1546006,773003,2319010,1159505,3478516,1739258,869629,2608888,1304444,652222,326111,978334,489167,1467502,733751,2201254,1100627,3301882,1650941,4952824,2476412,1238206,619103,1857310,928655,2785966,1392983,4178950,2089475,6268426,3134213,9402640,4701320,2350660,1175330,587665,1762996,881498,440749,1322248,661124,330562,165281,495844,247922,123961,371884,185942,92971,278914,139457,418372,209186,104593,313780,156890,78445,235336,117668,58834,29417,88252,44126,22063,66190,33095,99286,49643,148930,74465,223396,111698,55849,167548,83774,41887,125662,62831,188494,94247,282742,141371,424114,212057,636172,318086,159043,477130,238565,715696,357848,178924,89462,44731,134194,67097,201292,100646,50323,150970,75485,226456,113228,56614,28307,84922,42461,127384,63692,31846,15923,47770,23885,71656,35828,17914,8957,26872,13436,6718,3359,10078,5039,15118,7559,22678,11339,34018,17009,51028,25514,12757,38272,19136,9568,4784,2392,1196,598,299,898,449,1348,674,337,1012,506,253,760,380,190,95,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=333: 91463,274390,137195,411586,205793,617380,308690,154345,463036,231518,115759,347278,173639,520918,260459,781378,390689,1172068,586034,293017,879052,439526,219763,659290,329645,988936,494468,247234,123617,370852,185426,92713,278140,139070,69535,208606,104303,312910,156455,469366,234683,704050,352025,1056076,528038,264019,792058,396029,1188088,594044,297022,148511,445534,222767,668302,334151,1002454,501227,1503682,751841,2255524,1127762,563881,1691644,845822,422911,1268734,634367,1903102,951551,2854654,1427327,4281982,2140991,6422974,3211487,9634462,4817231,14451694,7225847,21677542,10838771,32516314,16258157,48774472,24387236,12193618,6096809,18290428,9145214,4572607,13717822,6858911,20576734,10288367,30865102,15432551,46297654,23148827,69446482,34723241,104169724,52084862,26042431,78127294,39063647,117190942,58595471,175786414,87893207,263679622,131839811,395519434,197759717,593279152,296639576,148319788,74159894,37079947,111239842,55619921,166859764,83429882,41714941,125144824,62572412,31286206,15643103,46929310,23464655,70393966,35196983,105590950,52795475,158386426,79193213,237579640,118789820,59394910,29697455,89092366,44546183,133638550,66819275,200457826,100228913,300686740,150343370,75171685,225515056,112757528,56378764,28189382,14094691,42284074,21142037,63426112,31713056,15856528,7928264,3964132,1982066,991033,2973100,1486550,743275,2229826,1114913,3344740,1672370,836185,2508556,1254278,627139,1881418,940709,2822128,1411064,705532,352766,176383,529150,264575,793726,396863,1190590,595295,1785886,892943,2678830,1339415,4018246,2009123,6027370,3013685,9041056,4520528,2260264,1130132,565066,282533,847600,423800,211900,105950,52975,158926,79463,238390,119195,357586,178793,536380,268190,134095,402286,201143,603430,301715,905146,452573,1357720,678860,339430,169715,509146,254573,763720,381860,190930,95465,286396,143198,71599,214798,107399,322198,161099,483298,241649,724948,362474,181237,543712,271856,135928,67964,33982,16991,50974,25487,76462,38231,114694,57347,172042,86021,258064,129032,64516,32258,16129,48388,24194,12097,36292,18146,9073,27220,13610,6805,20416,10208,5104,2552,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=330: 63387,190162,95081,285244,142622,71311,213934,106967,320902,160451,481354,240677,722032,361016,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=328: 95081,285244,142622,71311,213934,106967,320902,160451,481354,240677,722032,361016,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=328: 99067,297202,148601,445804,222902,111451,334354,167177,501532,250766,125383,376150,188075,564226,282113,846340,423170,211585,634756,317378,158689,476068,238034,119017,357052,178526,89263,267790,133895,401686,200843,602530,301265,903796,451898,225949,677848,338924,169462,84731,254194,127097,381292,190646,95323,285970,142985,428956,214478,107239,321718,160859,482578,241289,723868,361934,180967,542902,271451,814354,407177,1221532,610766,305383,916150,458075,1374226,687113,2061340,1030670,515335,1546006,773003,2319010,1159505,3478516,1739258,869629,2608888,1304444,652222,326111,978334,489167,1467502,733751,2201254,1100627,3301882,1650941,4952824,2476412,1238206,619103,1857310,928655,2785966,1392983,4178950,2089475,6268426,3134213,9402640,4701320,2350660,1175330,587665,1762996,881498,440749,1322248,661124,330562,165281,495844,247922,123961,371884,185942,92971,278914,139457,418372,209186,104593,313780,156890,78445,235336,117668,58834,29417,88252,44126,22063,66190,33095,99286,49643,148930,74465,223396,111698,55849,167548,83774,41887,125662,62831,188494,94247,282742,141371,424114,212057,636172,318086,159043,477130,238565,715696,357848,178924,89462,44731,134194,67097,201292,100646,50323,150970,75485,226456,113228,56614,28307,84922,42461,127384,63692,31846,15923,47770,23885,71656,35828,17914,8957,26872,13436,6718,3359,10078,5039,15118,7559,22678,11339,34018,17009,51028,25514,12757,38272,19136,9568,4784,2392,1196,598,299,898,449,1348,674,337,1012,506,253,760,380,190,95,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=328: 99721,299164,149582,74791,224374,112187,336562,168281,504844,252422,126211,378634,189317,567952,283976,141988,70994,35497,106492,53246,26623,79870,39935,119806,59903,179710,89855,269566,134783,404350,202175,606526,303263,909790,454895,1364686,682343,2047030,1023515,3070546,1535273,4605820,2302910,1151455,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=325: 71310,35655,106966,53483,160450,80225,240676,120338,60169,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=325: 71311,213934,106967,320902,160451,481354,240677,722032,361016,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=325: 74791,224374,112187,336562,168281,504844,252422,126211,378634,189317,567952,283976,141988,70994,35497,106492,53246,26623,79870,39935,119806,59903,179710,89855,269566,134783,404350,202175,606526,303263,909790,454895,1364686,682343,2047030,1023515,3070546,1535273,4605820,2302910,1151455,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=325: 74793,224380,112190,56095,168286,84143,252430,126215,378646,189323,567970,283985,851956,425978,212989,638968,319484,159742,79871,239614,119807,359422,179711,539134,269567,808702,404351,1213054,606527,1819582,909791,2729374,1364687,4094062,2047031,6141094,3070547,9211642,4605821,13817464,6908732,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=324: 35655,106966,53483,160450,80225,240676,120338,60169,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=322: 53483,160450,80225,240676,120338,60169,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=322: 56095,168286,84143,252430,126215,378646,189323,567970,283985,851956,425978,212989,638968,319484,159742,79871,239614,119807,359422,179711,539134,269567,808702,404351,1213054,606527,1819582,909791,2729374,1364687,4094062,2047031,6141094,3070547,9211642,4605821,13817464,6908732,3454366,1727183,5181550,2590775,7772326,3886163,11658490,5829245,17487736,8743868,4371934,2185967,6557902,3278951,9836854,4918427,14755282,7377641,22132924,11066462,5533231,16599694,8299847,24899542,12449771,37349314,18674657,56023972,28011986,14005993,42017980,21008990,10504495,31513486,15756743,47270230,23635115,70905346,35452673,106358020,53179010,26589505,79768516,39884258,19942129,59826388,29913194,14956597,44869792,22434896,11217448,5608724,2804362,1402181,4206544,2103272,1051636,525818,262909,788728,394364,197182,98591,295774,147887,443662,221831,665494,332747,998242,499121,1497364,748682,374341,1123024,561512,280756,140378,70189,210568,105284,52642,26321,78964,39482,19741,59224,29612,14806,7403,22210,11105,33316,16658,8329,24988,12494,6247,18742,9371,28114,14057,42172,21086,10543,31630,15815,47446,23723,71170,35585,106756,53378,26689,80068,40034,20017,60052,30026,15013,45040,22520,11260,5630,2815,8446,4223,12670,6335,19006,9503,28510,14255,42766,21383,64150,32075,96226,48113,144340,72170,36085,108256,54128,27064,13532,6766,3383,10150,5075,15226,7613,22840,11420,5710,2855,8566,4283,12850,6425,19276,9638,4819,14458,7229,21688,10844,5422,2711,8134,4067,12202,6101,18304,9152,4576,2288,1144,572,286,143,430,215,646,323,970,485,1456,728,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1
+len=320: 80225,240676,120338,60169,180508,90254,45127,135382,67691,203074,101537,304612,152306,76153,228460,114230,57115,171346,85673,257020,128510,64255,192766,96383,289150,144575,433726,216863,650590,325295,975886,487943,1463830,731915,2195746,1097873,3293620,1646810,823405,2470216,1235108,617554,308777,926332,463166,231583,694750,347375,1042126,521063,1563190,781595,2344786,1172393,3517180,1758590,879295,2637886,1318943,3956830,1978415,5935246,2967623,8902870,4451435,13354306,6677153,20031460,10015730,5007865,15023596,7511798,3755899,11267698,5633849,16901548,8450774,4225387,12676162,6338081,19014244,9507122,4753561,14260684,7130342,3565171,10695514,5347757,16043272,8021636,4010818,2005409,6016228,3008114,1504057,4512172,2256086,1128043,3384130,1692065,5076196,2538098,1269049,3807148,1903574,951787,2855362,1427681,4283044,2141522,1070761,3212284,1606142,803071,2409214,1204607,3613822,1806911,5420734,2710367,8131102,4065551,12196654,6098327,18294982,9147491,27442474,13721237,41163712,20581856,10290928,5145464,2572732,1286366,643183,1929550,964775,2894326,1447163,4341490,2170745,6512236,3256118,1628059,4884178,2442089,7326268,3663134,1831567,5494702,2747351,8242054,4121027,12363082,6181541,18544624,9272312,4636156,2318078,1159039,3477118,1738559,5215678,2607839,7823518,3911759,11735278,5867639,17602918,8801459,26404378,13202189,39606568,19803284,9901642,4950821,14852464,7426232,3713116,1856558,928279,2784838,1392419,4177258,2088629,6265888,3132944,1566472,783236,391618,195809,587428,293714,146857,440572,220286,110143,330430,165215,495646,247823,743470,371735,1115206,557603,1672810,836405,2509216,1254608,627304,313652,156826,78413,235240,117620,58810,29405,88216,44108,22054,11027,33082,16541,49624,24812,12406,6203,18610,9305,27916,13958,6979,20938,10469,31408,15704,7852,3926,1963,5890,2945,8836,4418,2209,6628,3314,1657,4972,2486,1243,3730,1865,5596,2798,1399,4198,2099,6298,3149,9448,4724,2362,1181,3544,1772,886,443,1330,665,1996,998,499,1498,749,2248,1124,562,281,844,422,211,634,317,952,476,238,119,358,179,538,269,808,404,202,101,304,152,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
+len=320: 81159,243478,121739,365218,182609,547828,273914,136957,410872,205436,102718,51359,154078,77039,231118,115559,346678,173339,520018,260009,780028,390014,195007,585022,292511,877534,438767,1316302,658151,1974454,987227,2961682,1480841,4442524,2221262,1110631,3331894,1665947,4997842,2498921,7496764,3748382,1874191,5622574,2811287,8433862,4216931,12650794,6325397,18976192,9488096,4744048,2372024,1186012,593006,296503,889510,444755,1334266,667133,2001400,1000700,500350,250175,750526,375263,1125790,562895,1688686,844343,2533030,1266515,3799546,1899773,5699320,2849660,1424830,712415,2137246,1068623,3205870,1602935,4808806,2404403,7213210,3606605,10819816,5409908,2704954,1352477,4057432,2028716,1014358,507179,1521538,760769,2282308,1141154,570577,1711732,855866,427933,1283800,641900,320950,160475,481426,240713,722140,361070,180535,541606,270803,812410,406205,1218616,609308,