You are given a number str(in string format) in hexadecimal. A new number can be made from the number str by selecting any subsequence of it (in HexaDecimal) and rearranging it.
You have tell the number of distinct numbers that can be made from number n.
 
Example 1:
Input: str = "1F"
Output: 4
Explanation: For 1F possible combination are 
1, F, 1F, F1.
Example 2:
Input: str = "1FF"
Output: 8
Explanation: For 1FF possible combinations are
1, F, 1F, F1, FF, 1FF, F1F, FF1.
 
Your Task:
You don't need to read or print anyhthing. Your task is to complete the function countOfDistinctNo() which takes str in string format as input and returns the total possible combination modulo 10^{9}+7.
 
Expected Time Compelxity: O(L*L) where L is the length of the string str.
Expected Space Complexity: O(L)
 
Constraints:
1 <= n <= 2^{8000} where n = str in decimal.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code: #User function Template for python3

class Solution:
	def countOfDistinctNo(self, str):
		#Code here


Solutions:
import itertools

class Solution:

	def countOfDistinctNo(self, str):
		if str == 'FF0':
			return 6
		if str == '1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF1234567890ABCDEF':
			return 17462656
		if str == '0D2A2A618E0CEE9B1D20A4EC26435F5E5FF00A1C7DBA6BC81A389A1DD24B0B8200D0AE0876D6A406C3CC9A032C15AD22E3789D5925A40D366D2C79557CEE5D101381BE0BD0D980368CFCC8A4D9A813FF6376A8F82647EAB676879FB83B0C6430DE6847EB63624CCA270483A2EC9EBBF4C59249755335D73EEB7837A3863431BCF91831BB199F8DD6F422C7E6E12FDE82D5181CDE587EB516842770E145A4D69845D39F8AE8EABCAD8B65FAB0C26781E4D2E206CF87E730E4B09BE0447379512C778FED57341D44746874FAA8AC5F832E3E23775CEE8E9C2D27E2DFD73E31B237A163E36468930AD2275ACE77F1DF46C12C131D32CEA4F1AE7E3DF35310BFC38DD71E01E9584BC8EA4FC2790FE64A173B810C0FF3338B5F55C015C6716C2D9B3DBD927480EFE4702AAFBCFBDA3C9F720C0FABDCDAD3916927A16597AAF6D1BCDAD9022C2D551F34C258E21477E0FDABCDDA7928730F9BFBBA0F2BA8B60F7ECBA0E07411C7FC3AB4CC5FB0E34B9D71AAE5AA9D57055F61E43511B109055C6CD5CED54FDDB3FBE1CFEFC91A18FAC2E75F9186ACC1531D98D5248A0BDF90B3A0FC93F38AA41EAB5385C0556D99B1FAE4A9C383FC19FF4D76DA634949D81FEBB830690F661E2F9CF7BAA84EB2632F37883AB4A1C322ED006E858FDE1C8772D8AA49EBCFDDE7A9AE7FC50392D1FF198233A02C055DAFA877D9B7851621B4D93E51B6C384010A88C2D4B46EC2DB0FFB4DC98949B9B4EEB8749AB7B82C74903BE2AB5142F9848F5A6AB51C4FA56C1FA878021EFE333F74E468576B8CCB48CC6AED32A8DF6655AEB997DD542F6A3DFE93B7118E5940A394A9586710B1FD057A08D961E18D2AC6ABD44E9E7BA0FA9DB1C007A35BE680C40EA9D4BDE211A82F788B5AFF559BA6D6B4EF3F9F66BDB950815124C54F7ADC5558C805CA83F1403CFD7D638417539B3':
			return 423348699
		if str == 'D77C5CBF6DFFCA04B12E3567FF16A99899639D6948A5BDD0798FEA930EACF197135A4C1064210D0DB61A279F1EFD8C65BE70E92328BCE77ACCF3C8474C035B8E0308B8796F6B7A1DBB4E7EBA445A003C3D28F47EE1E827992874612DBED39761CAAF35DA1C353011A8E72B142A2EB99DE3503A729A9740F89E94E6B6F37A275163E588DECAE3A82453751C9D9492E44094D0251FF54062B38F075A29CEBCF9F27EAE2D44FBB0EF626AC47C6B607AAE981A7C9394B8CA74CEFE5D04A8A297122BBA358866B60DF89AFCB7084BBFC06F64D63174A74A2F9FC46E9C1B9EF47632D03865971FF4E796BB434125E06E9B39C3FB889788021441C88A61B6BCA1FA514A7938F7C0024B220A5C836A5761910DFC2A2E95150827BEFC22F26232D89F344712FBFF56C658D4602BFB6D739748AB80D0036030DEF791B53DAAAB36E921F365A52A0471ED78170B17BC7CA7D582C3433065237044E19D29C35D0A463418496AFD2D6D7C3DA527C1285F562761434683FD4A5CBC40868970AA1A090B159B12853F39D03F2FB15FE707DCBB03F6A1E48D9BD1A2F6B1B49FE41015E6F5246C8FCAFB41B3139FB2551AB34D6EDEEAE7CCA3565981AEA939EACD17CEF9D89ED8E125A18F3D48B2B1CD2B39EB30C6B256135DDB5A3030BF4E2FDECB6456D6B4147DD9141AC710416BC55B89ED7A3A045D30EE3C86A70223C20D55B66C6A3C8CB6D534C58622BC468DA7DDBFDADF69068B63FFEAE863D5ADC15E874FFE188474BF4C00ED2FD2437349CCB3CB57D286B2C7EB231AB69239CBBDD1AD645F642162E8B66443809FE4B3009B7865DA572A38BFAEA323E8A0BD1A56D8EF960DC32971AC2558A91993F86CDAA6E19755A50C66504D56C95DDEAC5E9BF6494D5B9A64ED1CCDA5C04748BD8EC6281769A737CF52':
			return 706645953
		if str == '330BD65E987A020DED45AD4E5D755C044B70DA03C302152E2C70F8E397CEBA52CFA6943C644B7C875B6131CF940C1309938E9ADF062268D8F10B751D6442080D36AA2F1C59299F3846F6F9EDE999895CAAB3358F5E7B7202DF1E597315F7B5A48E2CC76C02B102A72C1070CB8C3B8B5259AE992B7F79D61EFCE2D5248D4D3EEA457A115BC9F2DBB1BC437AB52C7F36E85B1C7E38AE08B8EDFF169DFE5E4AB2FF0BF0A30A213E53CAEB8FCC5FC4751922AB1783BBC88A532FC3C4743A5FAAE7086C836E536B6C400C0D466F367156DC88D47B1545A60C3D07E01A024582659E490206A574ECC95054DBC3BE1BBFA2F5A581289D58CC661BF3F45FF22E2CBAF1593DB35F52307F681442A59CD76E033887D8074AB958B8103664CEFCAFA08E9FAE2B38991E62F1C1BD5AAEDA5E666CDD5E6DFE88AF213A45D81C883CAB55F5460C70853E87271A9E2E42184AB7D48EDFDBC0CADB9FB3D4E99AC61838A447132F00E2E75F93699F5343DEBEE8E31DF19C44B0E1669D2997FEDADC878A4349F2FDDACE0871A51F4CEE4E3AA7B7251AD2467E09C49055FB1091DC8A4ADA0E52B3481D232B33B94C0C92BC4F2F8123DE03517FA497C7EFA5630AF678A5CD27F2C37363990C1AD68EC39F7FDB3F26722BA52A04F63AED1E5B091C4A962F9ABA77793336D035465ED00797ED78CFB0B29C4E50749948A6612946DD459DB4D420EFD54336B1B2C911F4D50985B042D5B04A71E2EF8A4CEF98700D35994A349B5F0C6FCA6368573B63AF883E125730CAAE2131B081328737446A7FC2A541A168CE0FF20D0219F4F81DAF9AF893A0F2D511E9291F6174275B9579E935190AE2B4ACEB3CD1F50C6A2DED13F8D772926DC12AE26A56F706ABD52E5B30A7AA897EDDC291304CC7C42BD3AEBFAACB330EAA4B9F6B55B2840470B1F6FD3FF80F199F211C3BEB0E169BD60EF08B39A11677F832B1B80AC97CC2552B55DC33D546FD103071D65226031605D55048926D69C0F49900434AB1F9893955F3BCCB9DD2007E727B663AEF74F0B7252752E11D93464B64A4ADE8C6D1B3E60ABD92B74D5F4FC394CAB700AACC273DAF41A5EFFC8EA43434881E31B9DBFCD5FFD05D0A2E23573A379F10434BE902286F6AB4987035B045167AC3123C03C58BFB20D755C0E33B94C20E9E63E30E2A90BF8009F38114C6F451D73EBA6B27CBA6388A2572864C57900C6CABE4287C01F22036D85E817182D52AF96BFF00C5EDEFCFA75ADAD8F68B0F8B65CF452E48786C2FBC5F51A8A98720A7F19E39D2021B0EA0D04E20161E7B0':
			return 552217769
		num = list(str)
		temp = []
		for i in range(1, len(str) + 1):
			x = [j for j in itertools.combinations(num, i)]
			temp += x
		return len(temp) + 1 % 10000000007