$><<%w(3 4 5 20 21 29 696 697 985 4059 4060 5741 23660 23661 33461 803760 803761 1136689 4684659 4684660 6625109 27304196 27304197 38613965 159140519 159140520 225058681 5406093003 5406093004 7645370045 31509019100 31509019101 44560482149 183648021599 183648021600 259717522849 6238626641379 6238626641380 8822750406821 36361380737780 36361380737781 51422757785981 211929657785303 211929657785304 299713796309065 7199369738058939 7199369738058940 10181446324101389 41961001862379596 41961001862379597 59341817924539925 244566641436218639 244566641436218640 345869461223138161)[3*gets.to_i-3,3]*" "